CODEWITHSUNDEEP
pythonsieve-of-eratosthenes
Muhammad Zain
Muhammad Zain

Reputation: 25

Whats the purpose of using n+1 in this eratosthenes function?

Here is a simple eratosthenes sieve for prime numbers, which removes the multiples and append them in the empty list of multiples. My question is that if I use n instead of n+1 in both for loops the answer comes out the same.

def eratosthenes(n):
    multiples = []
    for i in xrange(2, n+1):
        if i not in multiples:
            print i
            for j in xrange(i*i, n+1, i):
                multiples.append(j)

returns output like

eratosthenes(10)
2
3
5
7

while if I replace n+1 with n in both loops the output is still the same:

def eratosthenes(n):
    multiples = []
    for i in xrange(2, n):
        if i not in multiples:
            print i
            for j in xrange(i*i, n, i):
                multiples.append(j)

returns the same output as above function...

eratosthenes(10)
2
3
5
7

My question is why we use n+1 instead of n?

Upvotes: 0

Views: 73

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1123400

The Python range() and xrange() functions, like the Python slice notation, do not include the end value; xrange(2, 10) generates 8 numbers from 2 to 9, not 10. n + 1 makes sure n is part of the generated range.

Use eratosthenes(7) or eratosthenes(11) to see the difference; 10 is not a prime number and is being filtered out.

Upvotes: 1

Related Questions