CODEWITHSUNDEEP
pythonpython-3.xprimesprimality-test
user10441782
user10441782

Reputation:

Why is my prime number checking code not displaying the correct output?

I have a code that checks whether a number is prime or not, and outputs "Yes" or "No" accordingly. But when I input 1763, it outputs "Yes" even though it isn't a prime. The code checks whether a number is prime or not by checking if it can be divisible by any number between 2 and n-1. So when I input 1763, it should output "No" because 1763 can be divisible by 41. What went wrong in my code?

def getNumber():
    n=int(input())
    return n

def isPrime(n):
    if n==2:
        print("Yes")
    else:
        for i in range (2,n):
            if n%i==0:
                print("No")
                break
            else:
                print("Yes")
                break

def main():
    n = getNumber()
    isPrime(n)

main()

Upvotes: 1

Views: 95

Answers (3)

Sheldore
Sheldore

Reputation: 39062

The problem is that you are not accounting for all the divisors. As soon as your first condition (if n%i==0:) is false, you execute the second elif condition and print "Yes".

Solution: You can use a flag which will be turned 1 only when a divisor will be found, which means the number is not prime. Below is slightly modified code of yours (showing only partial code, rest remains the same as yours). As pointed out by @bereal in the comments, you don't need to iterate up to n but only up to the square root sqrt(n). math.ceil returns the closest rounded off integer.

import math
def isPrime(n):
    flag = 0
    if n==2:
        print("Yes")
        return
    else:
        # for i in range (2, n):
        for i in range (2, math.ceil(np.sqrt(n)) + 1):
            if n%i==0:
                print("No")
                flag = 1
                break

    if not flag:
        print ("Yes")

1763
No

Upvotes: 1

blhsing
blhsing

Reputation: 106768

You should declare a number to be a prime only after you iterate through all the possible divisors without finding one. For that you can use the for-else construct instead, where the else block is only executed if the for loop isn't aborted with a break statement:

def isPrime(n):
    if n==2:
        print("Yes")
    else:
        for i in range (2,n):
            if n%i==0:
                print("No")
                break
        else:
            print("Yes")

Upvotes: 0

Johan
Johan

Reputation: 3611

In your loop you break on the first iteration, even if you haven't been able to prove that it isn't a prime yet.

You need to print yes only after you've checked all possible divisors up to n (it's actually enough to only check all numbers upp to the square of n).

for i in range (2,n):
    if n%i==0:
        print("No")
        return
print("Yes")

Upvotes: 0

Related Questions