http://www.perlmonks.org?node_id=442231

in reply to Rotationally Prime Numbers Revisited

I was going to suggest, as usual, that you use Math::Pari and the function isprime(), but your clever adjust method skips so many cases that even the brute-force prime checker you have is good enough. Math::Pari only buys you a fraction of a second.
• Comment on Re: Rotationally Prime Numbers Revisited

Replies are listed 'Best First'.
Re^2: Rotationally Prime Numbers Revisited
by Limbic~Region (Chancellor) on Mar 25, 2005 at 00:30 UTC
tall_man,
While Anonymous Monk suggested skipping all numbers containing (0, 2, 4, 5, 6, 8) in the original thread by YuckFoo, I independently thought of the idea on my own. I did borrow the 2/4 trick to avoid multiples of 3. The problem space reduction is amazing. In the first 1_000_000 numbers, only 4_220 candidates are tested. Out of those, 621* are eliminated as not being prime on the very first try.

I was going to use the C version of is_prime() from Re^3: a close prime number but as you saw yourself, it isn't needed.

Cheers - L~R

* Numbers ending in 5 (15 for instance) in the +2 portion of the code are included as candidates. It is possible to eliminate them but the work involved is more than allowing is_prime() to abort on the first try.
Here is a much faster approach. (I searched up to 10 billion in 10 minutes on my PC.) It looks at far fewer than yours does since it knows that it only looks at numbers whose digits are 1, 3, 7 and 9, and which furthermore have the largest digit first.
```#! /usr/bin/perl -w
use strict;

print "\$_\n" for 2, 3, 5, 7;
my @d = (1, 3, 7, 9);
my %seen;
for my \$length (2..(shift || 6)) {
# print "Length: \$length\n";
LIMIT: for my \$limit (0..3) {
my @indexes = \$limit - 1;
NUMBER: while (1) {
\$indexes[-1]++;
while (\$indexes[-1] > \$limit) {
pop @indexes;
next LIMIT unless @indexes;
\$indexes[-1]++;
}
while (@indexes < \$length) {
push @indexes, 0;
}
my \$num = join '', @d[@indexes];
for (1..\$length) {
next NUMBER unless is_prime_for_odds_over_3(\$num);
\$num =~ s/(\d)(\d*)/\$2\$1/;
}
for (1..\$length) {
print "\$num\n" unless \$seen{\$num}++;
\$num =~ s/(\d)(\d*)/\$2\$1/;
}
}
}
}

sub is_prime_for_odds_over_3 {
my \$n = shift;
my \$max = sqrt(\$n);
return 0 unless \$n % 3;
my \$div = 5;
while (\$div <= \$max) {
return 0 unless \$n % \$div;
\$div += 2;
return 0 unless \$n % \$div;
\$div += 4;
}
return 1;
}

It's already very fast, but you can improve it somewhat by doing your rotations with

```\$num = chop(\$num) . \$num;

Rate    s chop
s    258/s   -- -14%
chop 299/s  16%   --