Welcome to the Monastery PerlMonks

Re: Rotationally Prime Numbers

by particle (Vicar)
 on Jan 29, 2002 at 04:32 UTC ( #142243=note: print w/replies, xml ) Need Help??

in reply to Rotationally Prime Numbers

i wrote an algorithm to save you many, many cycles.

createPrimeVec() creates a bit vector of length \$max. the value is 0 if prime, 1 otherwise. it uses the sieve of erathosthenes method to create the list. merlyn wrote a column on this some time ago (suprise!)

isprime() is a simple bit vector lookup, very fast.

rotPrime() cleverly appends the return value of chop to the beginning of the string.

here it is:

```#!/usr/local/bin/perl -w
use strict;
\$|=1;

my \$vecPrime;
my %rotPrime;
# allows specification of a range, such as (1000, 9999)
my (\$min, \$max) = (2, 999_999);

print "---creating prime vector (length: \$max)\n";
\$vecPrime = createPrimeVec(\$max);
print "---created\n\n";

print "---trying rotations \$min..\$max\n";
for(\$min..\$max) {
next unless isprime(\$_);
my \$x = rotPrime(\$_);
\$x && \$rotPrime{\$x}++;
}
print "---tried \$min..\$max\n\n";
print "\$_\n" for(sort {\$a <=> \$b} keys %rotPrime);

#----------
# return list of prime numbers up to and including value passed (defau
+lt:1000)
sub createPrimeVec {
my \$UPPER = shift || 1000;
my \$sieve = "";
GUESS: for (my \$guess = 2; \$guess <= \$UPPER; \$guess++) {
next GUESS if vec(\$sieve,\$guess,1);
for(my \$mults = \$guess * \$guess; \$mults <= \$UPPER; \$mults += \$
+guess) {
vec(\$sieve,\$mults,1) = 1;
}    }
return \$sieve;
};

# returns true if found in prime number bit vector
sub isprime { return 1 if( vec(\$vecPrime,shift,1) == 0 ); };

# return smallest 'rotationally prime' number in set
# for instance, 1931, 9311, 3119, or 1193 yeilds return value 1193
sub rotPrime {
my (\$num, \$lchr, @list) = (shift);
for(1..length \$num) {
\$lchr = chop \$num;
\$num = \$lchr . \$num;
push @list, \$num;
return unless isprime(\$num);
}
return (sort @list)[0];
};
i had used the prime number code for a program using fermat's factoring algorithm. perhaps i'll post it, assuming there's not a module to do that already.

~Particle

Replies are listed 'Best First'.
Re: Re: Rotationally Prime Numbers
by YuckFoo (Abbot) on Jan 31, 2002 at 16:11 UTC
Thanks particle,

Great improvement. I purposefully didn't use the sieve method for memory considerations, but I see this is an ideal situation for vec. Something I've been aware of, but never really found a use for.

YuckFoo

Re^2: Rotationally Prime Numbers
by thinker (Parson) on Mar 25, 2005 at 08:39 UTC

i had used the prime number code for a program using fermat's factoring algorithm. perhaps i'll post it, assuming there's not a module to do that already.

Surely there was space in the margin to post it :-)

Create A New User
Node Status?
node history
Node Type: note [id://142243]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (3)
As of 2017-08-20 00:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (312 votes). Check out past polls.

Notices?