CODEWITHSUNDEEP
python
MINO
MINO

Reputation: 126

wondering why the incorrect result is from the is_prime function


def is_prime(x):
    for i in range(2,x):
        if (x % i) == 0:
            return False
        else:
            return True

print(is_prime(9))

this is my function to find the prime number, i am not sure why its always return True for 9, any helps and explanation? Thanks

Upvotes: 0

Views: 76

Answers (2)

QueenBee
QueenBee

Reputation: 107

Because 9%2 is 1, and that is True

Here is how I fixed your code

def is_prime(x):
  for i in range(2,x):
      if (x % i) == 0:
          return False
print(is_prime(9))

HOWEVER, this doesn't take into account of 0 and 1. So here is a more correct one

def is_prime(x):
  if(x==0 or x==1):
    return False
  for i in range(2,x-1):
      if (x % i) == 0:
          return False
  else:
      return True
print(is_prime(9))

Upvotes: -1

ouroboring
ouroboring

Reputation: 681

To understand why this is happening, take a look at what happens when 9 is passed into is_prime:

We enter the for loop, and set the initial value of i to be 2. Then, 9 % 2 = 1, not 0, so the if condition fails, and we go to the else condition, which then immediately returns True: But this isn't the definition of primality. We need that 9 is not divisible by any number smaller than it (apart from 1), not that it's not divisible by a single number. So, we can only return True once we've checked all the numbers in the range, like this:

def is_prime(x):
    for i in range(2,x):
        if (x % i) == 0:
            return False
    return True

Your code should now return the correct result for 9 (and, given infinite time, any natural number greater than 1).

A couple of things to think about: Do you need to check every number in range(2, x)? Perhaps you could look at what happens past the square root of x? Also, you might want to check if the number is less than 2 (i.e: 1, 0, -1, ...), because currently, your code will not give the correct result for these numbers. If you're interested also, the Sieve of Eratosthenes is a better algorithm than trial division for finding primes, which you might want to take a look at further down the line.

Upvotes: 2

Related Questions