CODEWITHSUNDEEP
pythonpython-3.xmathjupyter-notebookgoogle-colaboratory
Rafael Lima
Rafael Lima

Reputation: 420

Can't define 2 as prime number or not

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

Upvotes: 1

Views: 668

Answers (3)

ori6151
ori6151

Reputation: 592

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

Upvotes: 2

Onion
Onion

Reputation: 1

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

Upvotes: 0

Huw Thomas
Huw Thomas

Reputation: 317

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

Upvotes: 1

Related Questions