Can't define 2 as prime number or not

Question

I'm trying to define prime numbers, but my algorithm doesn't recognize 2 as a prime number. Instead return None. I try it in Google Colab, Jupiter Notebook and PyCharm with same result.

My code:

# V1) Test all divisors from 2 through n-1. (skip 1 and n)
def is_prime_v1(n):
  """ Return 'True' if 'n' is a prime number. False otherwise. """
  if n == 1:
    return False # 1 is not prime

  for d in range(2, n):
    if n % d == 0:
      return False # Is not prime
    return True

# ===== Test Function =====
for n in range(1, 21):
  print(n, is_prime_v1(n))

My output:

1 False
2 None
3 True
4 False
5 True
6 False
7 True
8 False
9 True
10 False
11 True
12 False
13 True
14 False
15 True
16 False
17 True
18 False
19 True
20 False

Additionally, the return has some erros, like 9 is not a prime number.

This code is from, starting in 0:46: Python and Prime Numbers || Python Tutorial || Learn Python Programming

Check your indentation. In general, go trough the code for the problematic cases with a pencil and paper and see what happens with each variable. When `n == 2`, what is `range(2,n)`? How many different values of `d` are checked in `n % d == 0`, when `n == 9`? — gstukelj, Oct 19 '19 at 16:01
more examples here if interested: https://stackoverflow.com/questions/15285534/isprime-function-for-python-language — Derek Eden, Oct 19 '19 at 16:09

ori6151 · Accepted Answer · 2019-10-19T16:47:59.550

Because Your program never enters the loop.

for d in range(2, n):
    if n % d == 0:
      return False # Is not prime
    return True

starts from 2, up until n-1. Also, you should indent it differently. Only after your program exited the loop should you return True:

for d in range(2, n):
    if n % d == 0:
      return False # Is not prime
return True

But if you want to optimize your function, it should be like this:

def is_prime_v1(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for d in range(3, round(n**0.5) + 1, 2):
        if n % d == 0:
            return False
    return True

Since you dont need to check up to the number itself, only it's square root. Also, no number that is even can ever be prime (except 2), since it would be divisible by two.
EDIT:
I'm happy my answer helped :)

score 1 · Answer 2 · answered Oct 19 '19 at 16:06

You can explicitly define 2 as prime.

The return True is inside your for loop and so is returning true after just 1 iteration (which is why you have errors).

For primes, it suffices to check only up to the square root of the number you are testing, this should speed things up considerably for large n.

Try this

def is_prime_v1(n):
  """ Return 'True' if 'n' is a prime number. False otherwise. """
  if n == 1:
    return False # 1 is not prime
  elif n == 2:
    return True

  for d in range(2, int(n**0.5) + 1):
    if n % d == 0:
      return False # Is not prime
  return True

score 0 · Answer 3 · answered Oct 19 '19 at 16:09

0

for d in range(2, n):
    if n % d == 0:
        return False # Is not prime
    return True

Create a separate if for it like you did for 1.

if n == 2:
    return True #2 is prime

answered Oct 19 '19 at 16:09

Onion

1
1

Can't define 2 as prime number or not

3 Answers3