is prime

MisterX b.xavier at internet.lu
Mon Dec 13 07:02:05 EST 2004 

Hi Raymond,

> But let me ask: are you saying that your number has 
> (approximately) 78 million digits? If so, this would take 
> some major work.

The number i got is larger than 10^1000000, so that's a billion digits!
Writing the number down as a string was very easy... Finding a prime in that
region was not as easy. Finding its roots is another... Finding a prime
canditate took around 1 month! Prooving it's a prime continues since...
Unfortunately I never found code for the Riehman-whoever solution.

It's true my code could be optimized and I do have an interface that caches
found primes and nonprimes. I also tried different codes but mine was fast
enough for the purpose of generating unique and large enough serial keys for
my registration manager... 

For speed and larger googols, I found this...

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

which has a code that might work but does seem limited by disk and ram
space. It does distributed clustered calculations which is the ideal thing
here. However, the author talks about problems in the numbers starting at
the trillions:

 "the biggest range you can investigate is (partitionSize) * 1,000,000,000,
where partitionSize is measured in GB. Today's commodity 240GB disks yield a
240,000,000,000 check range -- not even a trillion."

That sound unoptimistic but I only have one number to check. ;))

Cheers
Xavier
--
Go wild at MonsieurX.com


> -----Original Message-----
> From: metacard-bounces at lists.runrev.com 
> [mailto:metacard-bounces at lists.runrev.com] On Behalf Of 
> Raymond Griffith
> Sent: Sunday, December 12, 2004 14:13
> To: metacard at lists.runrev.com
> Subject: Re: is prime
> 
> (Trying this for the third time!)
> 
> > Simon said (gut pun!)
> > 
> >> Is there a function or command to tell me if a selected 
> line of a fld 
> >> is a prime number?  For example, a user selects line
> >> 3 of a fld, I'd like a true or false result to appear in 
> the message 
> >> box if that number is prime or not.  Or do I need to write 
> a little 
> >> function myself as no such feature exists?
> > 
> > Courtesy of http://MonsieurX.com - Free nitrous for RunRev 
> Naturally, 
> > you're encouraged to donate something to our paypal icon...
> > 
> > Here's a script I wrote and rewrite quite a bit over and over but 
> > which may not be totally optimized but which is quite fast 
> and precise 
> > (not all prime finding functions are exact!)... The only 
> limit to this 
> > program is the size handled by X in the IDE. In runrev, that's 
> > (2^32)-1 or (2^63)-1
> > 
> > Im waiting for a program to tell me if a 600MB ascii sized integer 
> > number is a prime since 5 months!
> > 
> >  function isPrime x
> >   if last char of x is in "0,5,2,4,6,8" then
> >     return false
> >   end if
> >    
> >   if x>3 and sumdigits(x) mod 3 = 0 then
> >     return false
> >   end if
> >   if x>17 and x mod 17 = 0 then
> >     return false
> >   end if
> >   if x>7 and x mod 7 = 0 then
> >     return false
> >   end if
> >   
> >   if x > 11 and x mod 11 = 0 then
> >     return false
> >   end if
> >    
> >   put (x div 2) into xfactors
> >   
> >   repeat with c = 2 to xfactors
> >     if last char of c is in "246805" then next repeat
> >     if x mod 3 > 0 then next repeat
> >     if x div c = 0 then
> >       return false
> >     end if
> >   end repeat
> >   return true
> > end isprime
> > 
> > function sumdigits x
> >   local z=0
> >   repeat for each char c in x
> >     add c to z
> >   end repeat
> >   return z
> > end sumdigits
> > 
> > A download is coming soon to MonsieurX.com... I guess i'll have to 
> > make a nice little gui for my primes finder stack after all... ;)
> 
> Hmmmm. This little function ought to run a bit faster for 
> smaller values. It also returns the smallest value which the 
> number is divisible by.
> 
> Function isPrime n
>   put 2 into k
>   if n mod k = 0 then
>     return "Composite",k
>   else
>     add 1 to k
>     put sqrt(n) into sqrtN
>     repeat while k<sqrtN
>       if n mod k = 0 then
>         return "Composite",k
>       else
>         add 2 to k
>       end if
>     end repeat
>   end if
>   return "Prime"
> End isprime
> 
> On the other hand, I see what you are doing for larger 
> values, you are trying to eliminate obvious composites from 
> the factor check.
> 
> You could do this for even numbers as I did here. I increment 
> by 2 after I finagle using 3 for a factor. So I am only using 
> odd-numbered factors.
> 
> And I also notice that you are examining n div 2 factors. 
> This is really unnecessary. If there are no factors of a 
> number n less than or equal to sqrt(n), then it is prime.
> 
> If you want to eliminate *all* composite factors from the 
> factor check, there are ways to do this with pretty fair 
> economy. It would be worth it in the long run if you are 
> working with monster-sized numbers, since it would reduce the 
> number of divisors you are working with. Some programs keep a 
> log of primes (or the equivalent) handy to work with numbers 
> of a certain size, then crank 'em out as needed after those 
> are exhausted.
> 
> I would be happy to discuss the process of division of large 
> number strings.
> There are a number of algorithms available to do this. Since 
> you are simply trying to find out whether a given number is 
> prime, the routine may be made a bit more simple. 
> 
> But let me ask: are you saying that your number has 
> (approximately) 78 million digits? If so, this would take 
> some major work.
> 
> Regards,
> 
> Raymond E. Griffith
> 
> 
> 
> > 
> > cheers
> > Xavier
> > 
> >> -----Original Message-----
> >> From: metacard-bounces at lists.runrev.com 
> >> [mailto:metacard-bounces at lists.runrev.com] On Behalf Of Simon Lord
> >> Sent: Wednesday, December 08, 2004 19:18
> >> To: MetaCard
> >> Subject: is prime
> >> 
> >> Is there a function or command to tell me if a selected 
> line of a fld 
> >> is a prime number?  For example, a user selects line
> >> 3 of a fld, I'd like a true or false result to appear in 
> the message 
> >> box if that number is prime or not.  Or do I need to write 
> a little 
> >> function myself as no such feature exists?
> >> 
> >> Sincerely,
> >> Simon
> >> 
> >> _______________________________________________
> >> metacard mailing list
> >> metacard at lists.runrev.com
> >> http://lists.runrev.com/mailman/listinfo/metacard
> >> 
> > 
> > _______________________________________________
> > metacard mailing list
> > metacard at lists.runrev.com
> > http://lists.runrev.com/mailman/listinfo/metacard
> 
> 
> _______________________________________________
> metacard mailing list
> metacard at lists.runrev.com
> http://lists.runrev.com/mailman/listinfo/metacard
>

More information about the metacard mailing list