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?
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.