Loading ...
Sorry, an error occurred while loading the content.

Re: Prime Numbers Algorithm

Expand Messages
  • maximilian_hasler
    Your algorithm can be more simply & efficiently be written as: for( n=2,1500, Ln=log(n)^log(log(n)^2) ; for(a=0,Ln, ; ; for(b=a,Ln, ; ; ; if( n==2 *a *b
    Message 1 of 4 , Sep 11, 2011
    View Source
    • 0 Attachment
      Your algorithm can be more simply & efficiently be written as:

      for( n=2,1500, Ln=log(n)^log(log(n)^2)
      ; for(a=0,Ln,
      ; ; for(b=a,Ln,
      ; ; ; if( n==2 *a *b +3*(a+b+1), next(3))
      ; ; )
      ; )
      ; print(2*n+3)
      )}

      Clearly 2*n+3 is never even, so if it is composite, it can be written as

      2n+3 = (2a+3)*(2b+3) (a>=0, b>=0)

      <=> 2n = 4ab + 6a + 6b + 6

      <=> n = 2ab + 3a + 3b + 3

      Your algorithm checks whether n can be written in that form,
      for all possible a,b < Ln.
      This is of course very inefficient
      (since the value of b is irrelevant for given a),
      it would be enough to check if 2n+3 is divisible by 2a+3.
      This would correspond to the (much more efficient) algorithm:

      for( n=2,1500, Ln=log(n)^log(log(n)^2)
      ; for(a=0, min(Ln,n-1), /* because Ln may be >> n !! */
      ; ; if( (2*n+3)%(2*a+3)==0, next(2))
      ; )
      ; print(2*n+3)
      )

      Moreover, it is sufficient to restrict yourself to
      2a+3 < sqrt(2n+3), i.e. a ~ sqrt(n/2)

      The bound you use is much too high for values of n < 10^30
      but it is not high enough beyond n ~ 10^35
      (you have Ln = sqrt(n) at n ~ 1.6 x 10^32, and then it is smaller).

      From there on you would be sure to find "wrong primes",
      if your program was not too inefficient as to do a check for n of this size.

      Maximilian
    Your message has been successfully submitted and would be delivered to recipients shortly.