Home › Blogs › garrett's blog ›

Project Euler Problem 35

garrett // Jun 15, 2009
//

I was apparently being OCD and put some time into the solution for Project Euler Problem 35.

Here we're trying to calculate the number of circular primes < 1,000,000. A circular prime is--well just read the problem statement.

Anyhow, here's a perl solution. It runs in about 5seconds, which isn't too bad, I guess -- could be faster.

  1. #!/usr/bin/perl -w
  2.  
  3. # get all circular prime numbers < 1000000
  4. # circular numbers are numbers where all rotations of a prime
  5. # are themselves simular
  6. # 197 is prime.  as are all rotations: 197, 971, 719.
  7.  
  8. use strict;
  9.  
  10. my $cache;
  11.  
  12. # pad results.  2 is circularlly prime, but no numbers which contain it are.
  13. my $count = 2;
  14.  
  15. # can filter out an numbers containing 2,4,5,6,8
  16. for(my $i = 1; $i < 1000000; $i++) {
  17.   next if($i =~ m/2|4|5|6|8/);
  18.   if(isPrime($i) && isCirc($i)) {
  19.     printf("%d: %d is circular\n", $count, $i);
  20.     $count++;
  21.   }
  22. }
  23.  
  24. sub isCirc {
  25.   my $x         = shift;
  26.   my $rotations = getRotations($x);
  27.   foreach my $rotation (@$rotations) {
  28.     return 0 if(!isPrime($rotation));
  29.   }
  30.   return 1;
  31. }
  32.  
  33. sub getRotations {
  34.   my $x = shift;
  35.   my @num = split(//, $x);
  36.   my @rotations;
  37.   for(my $i = 0; $i < @num; $i++) {
  38.     my $str;
  39.     for(my $j = $i; $j < @num; $j++) {
  40.       $str .= $num[$j];
  41.     }
  42.     for(my $j = 0; $j < $i; $j++) {
  43.       $str .= $num[$j];
  44.     }
  45.     push @rotations, $str;
  46.   }
  47.   return \@rotations;
  48. }
  49.  
  50. sub isPrime {
  51.   my $x   = shift;
  52.   return $cache->{$x} if($cache->{$x});
  53.   my $lim = sqrt($x)+1;
  54.   for(my $i = 2; $i < $lim; $i++) {
  55.     if(($x % $i) == 0) {
  56.       $cache->{$x} = 0;
  57.       return 0;
  58.     }
  59.   }
  60.   $cache->{$x} = 1;
  61.   return 1;
  62. }