CODEWITHSUNDEEP
python-3.x
Honey
Honey

Reputation: 43

My code for finding Prime Number is working fine but printing an unexpected value of 9. Explain how?

I have written a logic to find Prime Number up to some entered value. It is working fine but printing an unexpected 9 which don't go well with logic as 9%3 will be 0 and it have to skip that number.

n = int(input())
for i in range(2,n+1):
    for j in range(2,n+1):
        if i%j == 0 and i!=j:
            break
        else:
            print(i,end=" ")
            break

Input  : 20
Output : 2 3 5 7 9 11 13 15 17 19

Upvotes: 4

Views: 39

Answers (2)

hygull
hygull

Reputation: 8740

Just take a variable, e.g. is_prime to set it to True/False by checking if the number gets divided by any number in closed interval [2, n/2].

Do not decide immediately and come out of the loop once the if expression gets satisfied using break as you are doing.

With a tiny change in your code, you may make your code working and with less number of iterations (to decrease runtime complexity) as follows. 

n = int(input())
for i in range(2,n+1):
    is_prime = True
    for j in range(2, n//2 + 1):
        if i % j == 0 and i != j:
            is_prime = False
            break
    if is_prime:
        print(i, end= " ")

Upvotes: 0

blhsing
blhsing

Reputation: 106883

You output a candidate number as soon as it is found not divisible by any other number, so for the candidate number 9, as soon as the inner loop starts with the divisor number 2, it would immediately go into the else block and output the number and break the inner loop because 9 is not divisble by 2.

You should wait until all the divisors from the inner loop have exhausted before deciding that the candidate number from the outer loop is indeed a prime number, and for that you can use the for-else construct:

n = int(input())
for i in range(2, n + 1):
    for j in range(2, n + 1):
        if i % j == 0 and i != j:
            break
    else:
        print(i, end=" ")

Sample input/output:

20
2 3 5 7 11 13 17 19

Upvotes: 3

Related Questions