python - Prime numbers using sieve of erathosthenes

Question

So I am new to programming in python(and in general) and was doing some coding challenges. I came across this 'prime numbers using the sieve method' challenge. I have successfully managed to attempt it however I feel like my logic needs improvement.

So what I did was use 3 while loops in python, the code works as intended, gives me a set of prime numbers however I cannot find a way to condense it.

import sys
n = int(sys.argv[1])
ls = []
i = 2
while i <= n:
    ls.append(i)
    i += 1

i = 0
while i < len(ls):
    if i == 0:
        pass
    else:
        ls[i] = ''
    i += 2

i = 1
while i < len(ls):
    if i == 1:
        pass
    else:
        ls[i] = ''
    i += 3

i = 0
while i < len(ls):
    if i == 0:
        pass
    else:
        ls[i] = ''
    i += 5

i = 0
primes = []
while i < len(ls):
    if ls[i] != '':
        primes.append(ls[i])
    i += 1

for prime in primes:
    print(prime,end=', ')

As the ceo of nvidia once said, 'it just works' but clearly not in the best way :D

标签： python

Answer 1

Your code thinks 49 is prime, which is not awesome. Making a while loop for each prime just doesn't work.

Here's a simple version that does:

import math

def primesLessThan(N):
    seive = [True] * N
    seive[0] = seive[1] = False
    for i in range(2,int(math.sqrt(N))+1):
        if (seive[i]):   # i is prime
            for j in range(2*i,N,i):   # all multiples of i >= 2i
                seive[j] = False       # j is composite since i is a factor
    return [p for p in range(2,N) if seive[p]]

print(primesLessThan(500))