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

Prime Numbers Algorithm

Expand Messages
  • Sebastian Martin Ruiz
    Hi Here I send you that I have obtained a MATHEMATICA algorithm to obtain the prime numbers based on ideas Ragheb and Thamer Masarweh. Two questions: Is that
    Message 1 of 4 , Sep 11, 2011
    View Source
    • 0 Attachment
      Hi


      Here I send you that I have obtained a MATHEMATICA algorithm to obtain the prime numbers based on ideas
      Ragheb and Thamer Masarweh.

      Two questions:

      Is that correct?

      Is polynomial?

      Do[a=0;b=0;Ln=Log[n]^Log[Log[n]^2];c=1;
        While[a<Ln,c=1;
          While[b<Ln,nab=Abs[n/(2 a b +3(a+b+1))-1];
            If[nab==0,c=n;b=Ln+1;a=Ln+1,b=b+1]];a=a+1;b=a];
        If[c<n,Print[2n+3," ",PrimeQ[2n+3]]],{n,2,1500}]

      Sincerely

      Sebastian Martin Ruiz

      [Non-text portions of this message have been removed]
    • maximilian_hasler
      What do you mean by polynomial ? The most naive algorithm, for n from 2 to N_max for k from 2 to sqrt(n) if n mod k = 0 then next n end for k print n /*
      Message 2 of 4 , Sep 11, 2011
      View Source
      • 0 Attachment
        What do you mean by "polynomial" ?
        The most naive algorithm,

        for n from 2 to N_max
        for k from 2 to sqrt(n)
        if n mod k = 0 then next n
        end for k
        print "n" /* it's prime */
        end for n

        also is polynomial, less than O(N_max)^2.

        Maximilian

        --- In primenumbers@yahoogroups.com, Sebastian Martin Ruiz <s_m_ruiz@...> wrote:
        >
        >
        >
        > Hi
        >
        >
        > Here I send you that I have obtained a MATHEMATICA algorithm to obtain the prime numbers based on ideas
        > Ragheb and Thamer Masarweh.
        >
        > Two questions:
        >
        > Is that correct?
        >
        > Is polynomial?
        >
        > Do[a=0;b=0;Ln=Log[n]^Log[Log[n]^2];c=1;
        > � While[a<Ln,c=1;
        > ��� While[b<Ln,nab=Abs[n/(2 a b +3(a+b+1))-1];
        > ����� If[nab==0,c=n;b=Ln+1;a=Ln+1,b=b+1]];a=a+1;b=a];
        > � If[c<n,Print[2n+3," ",PrimeQ[2n+3]]],{n,2,1500}]
        >
        > Sincerely
        >
        > Sebastian Martin Ruiz
        >
        > [Non-text portions of this message have been removed]
        >
      • 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 3 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.