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