is prime

[Raymond Griffith]

(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