Welcome, guest | Sign In | My Account | Store | Cart

Using the Sieve of Eratosthenes find the first n primes numbers.

Python, 12 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12``` ```def prime(n): def z(x): if x :return True return False num1=range(0,n+1); num2=int(n**0.5) +1 for k in range(2,num2): num0=range(k,n+1,k);del num0[0] for i in num0: num1[i]=0 return filter(z, num1) print prime(102) ```

Liu Xiaowei 7 years, 2 months ago

Hello, Your code is very concise. But I don't think it's efficient. The time cost of your code is n(n*0.5)

``````n = 1000000
i = 2
result = []
while i < n:
flag = True
for item in range(2, int(i**0.5)+1):
if i % item == 0 and i != item:
flag = False
break
if flag:
result.append(i)
i += 1

print(result)
``````

My code is not good either, but I think its time cost is better than yours. For example, when I set n = 1000000, your code cost 15 seconds while mine cost 12 seconds on my computer.

Liu Xiaowei 7 years, 2 months ago

The time cost of your code is n*(n**0.5)

juan (author) 7 years, 2 months ago

Liu you are right now is n(n**0.5)/2 thanks

 Created by juan on Sun, 17 Aug 2014 (MIT)