Sorry, an error occurred while loading the content.

## 21714RE: [PrimeNumbers] Web page:

Expand Messages
• Aug 12 4:58 AM
> 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]
• Show all 2 messages in this topic