0
\$\begingroup\$
print("Welcome to the Sieve of Eratosthenes, where you can generate prime numbers from 1 to n  : ")
n = int(input("Enter your n :   "))
y = [y for y in range(1,n) if y*y < n]
primes = [p for p in range(2,n+1)]
length = len(primes)

print(primes)

for p in range(2,len(y)+2):
    
    for i in range(2,length+1):
        if(i%p == 0 and i != p ):
            if(i in primes):
                primes.remove(i)
        
                
print(primes)
            


"""
1.)A range  //0 to 100  .x
2.)Multiples can be found using 1 to sqrt(n) .x
3.)Now eliminate all multiples. x
"""

OUTPUT

Enter your n : 20
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[1, 2, 3, 5, 7, 11, 13, 17, 19]

So I did this by my own and also I need some suggestions on what can I do to improve the code and can you tell me how good it is?.

\$\endgroup\$
2
  • \$\begingroup\$ i've updated the code,could you recheck it again \$\endgroup\$
    – Aryan
    Sep 11 at 9:24
  • 1
    \$\begingroup\$ This always returns that the last number is prime. E.g. n=125 or n=102 return 125 and 102 as prime respectively. No numbers that end in 2 or 5 are prime except 2 and 5 themselves. \$\endgroup\$
    – mdfst13
    Sep 11 at 10:31
2
\$\begingroup\$
print("Welcome to the Sieve of Eratosthenes, where you can generate prime numbers from 1 to n  : ")

This is not a Sieve of Eratosthenes. It is a prime sieve in the sense that it takes a list of numbers and removes (or sieves) out those that aren't prime. But it does not follow the algorithm of the Sieve of Eratosthenes.

Here's what the Sieve of Eratosthenes looks like:

primes = [p for p in range(2, n + 1)]

for p in primes:
    if p > n / p:
        break

    for i in range(p * p, n + 1, p):
        if i in primes:
            primes.remove(i)

This is not necessarily the optimal version (for example, it might be better to compare p to the square root of n rather than do the n / p each time; or it may be better to use a set rather than a list). Nor is it likely to be the most Pythonic. I don't do Python development, so you should not take anything I suggest as being Pythonic.

Some things that this does that your version does not:

  1. It only works on numbers that are prime. The initial loop may look like it is iterating over the entire range. But it actually only iterates over the primes, because the non-primes have been removed before it reaches them (I tested and unlike PHP, Python iterates over the current version of the array, not a copy of the original). It starts with 2 and eliminates all the even numbers.
  2. It does no trial division. Instead, it uses the Eratosthenes method of taking multiples of the current prime.

That piece about multiplying rather than dividing is what I would describe as the central principle of the Sieve of Eratosthenes algorithm. So when I say that your version is not a Sieve of Eratosthenes, I mean that it doesn't do that.

Note: there is nothing wrong with implementing a different sieve. It's possible to write a better one (although I'm not convinced that this is better). The Sieve of Eratosthenes is notable for being relatively good as well as comprehensible with moderate effort. It's not the best performing sieve. I'm just saying that you shouldn't call your version a Sieve of Eratosthenes, as it isn't one.

\$\endgroup\$
1
  • \$\begingroup\$ I like how your SoE code removes values from the list while you're iterating it. Setting a good example here :-) \$\endgroup\$ Sep 12 at 6:56
1
\$\begingroup\$

Stylistic improvements

  • You create a list y, and only use it to have an upper bound for the first loop. The bound should be the square root of n, you can compute that directly. So for p in range(2, math.ceil(n**0.5) + 1) instead of for p in range(2, len(y)+2).
  • In Python you don't need (and shouldn't use) parenthesis for if statements. if i in prime is the same thing as if (i in prime).
  • If you look closely, you will notice that length is just the same as n-1. That's actually an error, as you include the number n into list primes of potential prime numbers. E.g. if n = 99, it will not eliminate 99 because of that. Anyway, you can just use n instead of length.

After those suggestions, and bug fixes you end up with the following code:

import math
n = int(input())

primes = [p for p in range(2, n + 1)]
for p in range(2, math.ceil(n**0.5) + 1):
    for i in range(2, n + 1):
        if i % p == 0 and i != p:
            if i in primes:
                primes.remove(i)

print(primes)

Algorithmic improvements

Lets first run the program for n = 100 000. On my laptop the code takes about 2.5 minutes to run.

One big mistake is, that you use a list to store the potential prime numbers. If you maintain the potential numbers on paper, it's actually pretty quick to look up if a number is in the list, because the numbers are ordered increasingly. Also it's easy to remove a number. E.g. if you want to remove the number 4 from the list, you know that it's right at the beginning and you can just cross it out with a pen. However Python doesn't know that this list is monotonically increasing. If you want to remove the number 4 from the list of 100 000 numbers, then it has to check all 100 000 numbers, as any of those could be a 4. So you waste a lot of time. In terms of complexity, both looking up numbers (if i in primes) and removing a number primes.remove(i) is O(n)).

There are other data structures, that can do both operations a lot faster. The easiest is just to use a Python set. A set is just a data structure that can hold a bunch of different numbers. It doesn't care about the order or how often you insert a number ({1, 2} == {2, 1, 1} is True in Python), however you can make lookups really fast and can also remove values really fast. Both in O(1) in Python.

And as a side note. if i in primes: primes.remove(i) is the same as primes.discard(i). discard removes an element from a set if it is there, and does nothing if it isn't there.

import math
n = int(input())

primes = set(range(2, n + 1))
for p in range(2, math.ceil(n**0.5) + 1):
    for i in range(2, n + 1):
        if i % p == 0 and i != p:
            primes.discard(i)

print(sorted(primes))

Notice that we sort the remaining numbers at the end, as a set in Python doesn't keep the data in sorted order (at least it's not guaranteed).

For the same input (n = 100 000), the code runs in about 2.7 seconds now. Almost speedup of 60x.


If you study the Sieve of Eratosthenes a bit, you will realize that you only need to cross out multiples of prime numbers. E.g. we i == 6 you don't need to cross out any multiples of 6 any more, because we crossed them out already when we crossed out multiples of 2 (and in fact a second time when we crossed out multiples of 3).

That means we can do the following optimization:

import math
n = int(input())

primes = set(range(2, n + 1))
for p in range(2, math.ceil(n**0.5) + 1):
    if p in primes:
        for i in range(2, n + 1):
            if i % p == 0 and i != p:
                primes.discard(i)

print(sorted(primes))

For the input n = 100 000 this runs now in just 0.7 seconds.


Another optimization could be the following. Currently you run i over all numbers, and check if they are multiples of p. But you can also just iterate over all multiples of p directly. Since we know that all multiples of p are 2*p, 3*p, 4*p, 5*p, ..., you can just run the following:

import math
n = int(input())

primes = set(range(2, n + 1))
for p in range(2, math.ceil(n**0.5) + 1):
    if p in primes:
        for k in range(2, n // p + 1):
            primes.discard(k * p)

print(sorted(primes))

This now runs in just 0.12 seconds for the input n = 100 000. A total speedup of over 1000x starting from the initial code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.