Prime numbers in a given range using Sieve of Eratosthenes
<p>I am trying to print prime numbers less than 'n'.The code is below:</p>

<pre><code>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)
</code></pre>

<p>Output for</p>

<pre><code>prime_numbers(10) 
</code></pre>

<p>is </p>

<pre><code>0
1
2
3
5
7
9
</code></pre>

<p>The program correctly prints for 100. What changes do I need to make?</p>

<p>The end point in a <code>range()</code> is not included. Since <code>sqrt(10)</code> is <code>3.1623</code>, your <code>range()</code> 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).</p>

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

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

<p>You want to <em>add one</em> to the floored square root to make sure it is tested for:</p>

<pre><code>for i in range(2, int(sqrt(n)) + 1):
</code></pre>

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

<pre><code>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)
</code></pre>

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

<p>Demo:</p>

<pre><code>&gt;&gt;&gt; prime_numbers(31)
2
3
5
7
11
13
17
19
23
29
31
</code></pre>

<p>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.</p>

python python-3.x primes