1

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()
ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • Possible duplicate of [What is the best algorithm for checking if a number is prime?](https://stackoverflow.com/questions/1801391/what-is-the-best-algorithm-for-checking-if-a-number-is-prime) – khelwood Oct 15 '18 at 10:38
  • You're breaking out of the for loop on the first iteration so it never gets down to 41 – Sayse Oct 15 '18 at 10:38
  • 1
    Your `for` loop breaks as soon as it finds a number that is not a factor. It needs to keep going until it finds a number that is a factor. You can only say it's prime after you have finished the whole for loop and not found any factors. – khelwood Oct 15 '18 at 10:39
  • I took away the 2 breaks, and it still gives me the wrong output. –  Oct 15 '18 at 10:40

3 Answers3

1

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
Sheldore
  • 37,862
  • 7
  • 57
  • 71
0

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")
Johan
  • 3,577
  • 1
  • 14
  • 28
0

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")
blhsing
  • 91,368
  • 6
  • 71
  • 106