pythonpython-3.xprimesprimality-test

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()

Solution

  • 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