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

RE: [PrimeNumbers] Web page:

Expand Messages
  • Matteo Mattsteel Vitturi
    ... Very funny: I ve ported it as is in Python but it is very slow. import math def prime3(n): Prime numbers generator t = 1 lim = 2 * int( n *
    Message 1 of 2 , Aug 12, 2010
    • 0 Attachment
      > Date: Wed, 11 Aug 2010 14:48:32 +0000
      > Subject: [PrimeNumbers] Web page:
      > Hello all:
      > This is mi new web page (in spanish and english).
      > http://www.numerosprimos.net/
      > sincerely
      > Sebastián Martín Ruiz

      Very funny: I've ported it "as is" in Python but it is very slow.



      import math

      def prime3(n):

      """Prime numbers generator"""

      t = 1

      lim = 2 * int( n * math.log(n) ) + 1

      for k in range(1, lim+1):

      t += 1

      f = 0

      for j in range(2, k+1):

      g = 0

      for s in range(1,j+1):

      g += (j // s) - ((j-1) // s)

      f += 1 + ( -(g-2) // j )

      t -= f // n

      return t



      I succeed in reducing one for-loop buffering common elements of sums, but it is again slower than eratosthenes sieve.



      def prime2(n):

      """Prime numbers generator (better)"""

      t = 1

      lim = 2 * int( n * math.log(n) ) + 1

      af = [0, 0]

      f = 0

      for j in range(2, lim+1):

      g = 0

      for s in range(1, j+1):

      g += (j // s) - ((j-1) // s)

      h = -(g-2) // j

      f += 1 + h

      af.append(f)

      for k in range(1, lim+1):

      t += 1

      f = af[k]

      t -= f // n

      return t




      In few seconds, this one proves to work for all n < 1000. Duration increases very quickly, so I tested some samples n < 20000.

      It would be fine if it were possible to further reduce the two nested for-loops.
      M.







      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.