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

First n primes numbers (Python recipe) by juan
ActiveState Code (http://code.activestate.com/recipes/578923/)

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

Python, 12 lines
Download
 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)

3 comments

Liu Xiaowei 9 years, 7 months ago  # | flag

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 9 years, 7 months ago  # | flag

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

juan (author) 9 years, 7 months ago  # | flag

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

Created by juan on Sun, 17 Aug 2014 (MIT)
◄ Python recipes (4591) ►
◄ juan's recipes (6) ►

Required Modules

Other Information and Tasks