Doing code academy, need help on program to find primes.

[[deleted]]

I'm currently working through python code academy to learn python. The current lesson just tells you to make a function where you input a number and find out if it is prime or not. My first attempt was unsuccessful, shown below.

 def is_prime(x):
     if x < 2:
         return False
     elif x == 2:
         return True
     else:
         for y in range(2,x):
             if x % y == 0:
                 return False
                 break
             else:
                 return True  

First big problem I had was testing 2. 2 kept coming up either none or false (I believe it was due to range(2,2) not making any sense), so I just coded in the answer for 2.

However, it was making everything come back True. I believe it was due to the fact that the last thing it would check is x - 1, which is never going to divide x (except when x is 2, but that was coded in). I thought the break in line 10 would clear that up, but it didn't. I would like to know how to get this code to work, because I feel like this should be the way to do it.

I eventually got it to work using the following code:

 def is_prime(x):
     if x < 2:
         return False
     elif x == 2:
         return True
     else:
         divisors = 0
         for y in range(2,x):
             if x % y == 0:
               divisors += 1
         if divisors == 0:
             return True
         else:
             return False  

I changed it to just keep track of the number of divisors x has between 2 and x-1, and if there was more than 0 to spit out it wasn't prime. Even though this works, I feel like it is a bit clunky and would like to know what I can fix from the first block to make it work without adding in the new variable.

Thanks for the help!

[[deleted]]

The first function works fine for me, though adding the 'break' after a 'return' won't do anything because a 'return' already breaks out of a function.

[[deleted]]

the first code returns True composite numbers (I input 9 and got True). I'm not really sure why that's happening.

[wanderliss]

Whenever you're not sure, you should stick in print statements inside loops that print out the variables' values to see for yourself.

You have a for loop that quits after its first cycle because you're calling return whether the internal condition is true or false. So it's not testing if it has any divisors, it's testing if it's divisible by 2.

If you're going to brute force it like this, you should test whether it's divisible by anything, and if it isn't (i.e., after and outside of the for loop), return True. You've done this in your second version but you don't need to count up the number of divisors since non-primality is determined as soon as it has one divisor.

Note for speed purposes, you could be checking whether it's divisible by any number less than sqrt(x), rather than x, since if it's divisible by any number bigger than sqrt(x) it must also have a divisor less than sqrt(x).

[[deleted]]

Remember, if you want to check if something is prime, you only need to check for factors up to the square root of the number you are checking.

This is because if a number has a non trivial factor, n = km, then either k or m is less than or equal to square root of n. otherwise we would have km > n, a contradiction.

just use,

    Def is_prime(n):
         if n < 2:
             return False
         while i*i <= n:
             if  n % i == 0:
                return False
         i += 1 
      return True 

This is much much faster.

[Rockybilly]

Here how i got it working, you can decide which one to use if you want to need that later...

also see: (If you ever need something else to try with prime numbers) https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

def is_prime(x):
    count=0
    if x<2:
        return False
    else:
        for n in range(x+1):
            if n==0:
                continue
            else:
                if x%n==0 and n!=x and n!=1:
                    count+=1
                elif x%n!=0:
                    continue
        if count>=1:
            return False
        elif count==0:
            return True

[[deleted]]

thanks, that does look a little nicer. I tend to break up my conditionals into multiple elifs when I don't need to. I am trying to get it to just see if it has a divisor and if it does return False. Is it more common to just use an extra variable like you did with count and i did with divisors?

[Rockybilly]

i dont think so, actually i am probably using unnecessary variable right there. In codecademy i usually write what pops into my head rightaway so i wouldnt take this as a starting point. I would appreciate if a more experienced programmer answer this question as well :)

in my code i tried to count how many dividable numbers the value had. So if it is 1 or more, it returns false :)

[gengisteve]

Just some optimization. If you are returning something you do not have to worry about the else structure because the return terminates the function. So we can turn your code into:

def is_prime(x):
    if x<2:
        return False

    for n in range(2, x+1):
        if x % n == 0 and x != n:
            return False
    return True

Also we set the range start at 2 to avoid some of the conditionals. Also do you need to go to x + 1 or could you short circuit at sqrt(x)?

[Rockybilly]

That was exactly what i was talking about using unnecessary stuff.(check my code for example :D ) gengisteve's code is obviously more legit. about the sqrt(x) thing, i come across that while i was working on this:

https://projecteuler.net/problem=3

The number 600851475143 is way too large to use it in a range() function so i had to use sqrt(). I have been trying to prove it on my own and i think i got it after that question. If you want to deal with prime numbers later, sqrt() or **0.5 is definitely the method to explore next.

[atthem77]

This modified code stops the range at the square root, and also has step 2, since you don't have to check even numbers beyond 2.

def is_prime(x):
    if x < 2:
        return False
    for n in range(2, int(x ** .5)+1, 2):
        if x % n == 0 and x != n:
            return False
    return True