CODEWITHSUNDEEP
pythonpython-3.xprimes
shubhamj
shubhamj

Reputation: 938

Prime numbers in a given range using Sieve of Eratosthenes

I am trying to print prime numbers less than 'n'.The code is below:

def prime_numbers(n):
    A=[1 for i in range(n+1)]
    for i in range(2,int(sqrt(n))):
        if A[i]==1:
            for j in range(i*2,n,i):
                A[j]=0
    for i in range(n):
        if A[i]:
            print(i)

Output for

prime_numbers(10)

is 

0
1
2
3
5
7
9

The program correctly prints for 100. What changes do I need to make?

Upvotes: 1

Views: 674

Answers (2)

Andy Richter
Andy Richter

Reputation: 189

I used slicing [...] = False * (...) to set the ranges to False.

from math import ceil,isqrt
def prime_numbers(n):
    sieve = [True] * (n)  # create a list n elements long
    sieve[0] = sieve[1] = False
    for i in range(2, isqrt(n)+1):
        if sieve[i]:
            sieve[i*2:n:i] = [False]*(ceil(n / i) - 2)
    return sieve 

p = prime_numbers(1000000) # get a million primes
print(f"primes from 1 to 100 {[i for i in range(1,101) if p[i]]}") 

print(f"primes from {len(p)-100} to {len(p)}  {[i for i in range(len(p)-100,len(p)) if p[i]]}")

The output looks like:

$ time python test.py 
primes from 1 to 100 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
primes from 999,900 to 1,000,000  [999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]

real    0m0.060s
user    0m0.052s
sys 0m0.008s

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1123072

The end point in a range() is not included. Since sqrt(10) is 3.1623, your range() loops to 2 and no further, and the multiples of 3 are not removed from your list. Your code works for 100, because it doesn't matter if you test for multiples 10 (those are already covered by 2 and 5).

The same issue applies to your other loops; if you want to include n itself as a candidate prime number you should also include it in the other ranges.

Note that you also want to ignore 0 and 1, those are not primes. You could add A[0] = A[1] = False at the top to make sure your last loop doesn't include those, or start your last loop at 2 rather than 0.

You want to add one to the floored square root to make sure it is tested for:

for i in range(2, int(sqrt(n)) + 1):

I'd use booleans rather than 0 and 1, by the way, just for clarity (there is not much of a performance or memory footprint difference here):

def prime_numbers(n):
    sieve = [True] * (n + 1)  # create a list n elements long
    for i in range(2, int(sqrt(n)) + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = False
    for i in range(2, n + 1):
        if sieve[i]:
            print(i)

I used [..] * (n + 1) to create a list of n items (plus 0); this produces a list with n shallow copies of the contents of the left operand. That's faster than a list comprehension, and the shared references are fine since True is a singleton in Python.

Demo:

>>> prime_numbers(31)
2
3
5
7
11
13
17
19
23
29
31

Note that 31 is included there; your code would have resulted in incorrect output as you'd have left in all the multiples of 5.

Upvotes: 2

Related Questions