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;
}
|