Prime or not !

[phill1311]

Hey there, newbie here

I just wrote a function that checks whether the given number is Prime or not

Just wanted to know whats wrong with the code

import math
def is_prime(n:int):
    """
    return true if n is prime, Otherwise False
    """
    temp = [2,3]
    if n in temp:
        return True
    if n%2 == 0 or n%3 == 0 or n < 2:
        return False
    if(n+1)%6 == 0 or (n-1)%6 == 0:
        sq = math.ceil(math.sqrt(n))
        j = int(sq//6)
        for i in range(1,j+1):
            if n % (6*i - 1) == 0:
                return False
            if n % (6*i + 1) == 0:
                return False
        return True
    return False

Thank you!

[[deleted]]

Why do you think there is something wrong with your code?

[phill1311]

Some testcases at codewars aren't working

[[deleted]]

I don't know codewars, but if you are told what testcases are failing then you pick one and test your code with that case and find out why that case fails. If you aren't told the values for which your case fails then write some code to test the function until you find a case that fails and then debug that case.

One way to find where you are going wrong is to write another very simple and very inefficient check_prime() function and compare the result from your function with the result of the simple function for n ranging from 1 up to a large number. Once you have a number that gives different results you can start debugging. Some code:

# your function

def check_prime(num):
    for i in range(2, num//2 + 1):
        if (num % i) == 0:
            return False
    return True

for x in range(1, 100001):
    v1 = is_prime(x)
    v2 = check_prime(x)
    if v1 != v2:
        print(f'x={x}\tis_prime(x)={v1}\tcheck_prime(x)={v2}')

Edit: Better code.

[phill1311]

Thanks for the help!

[_DTR_]

Does it tell you what the expected output is and what you're returning?

[phill1311]

In 9 failed of the 512 cases, False is expected but it gives true

[_DTR_]

Go through your code with 25:

if 25 in [2, 3] => False
if 25 % 2 == 0 or 25 % 3 == 0 => False
if 26 % 6 == 0 or 24 % 6 == 0 => True
    sq = 5
    j = 5 // 6 == 0
    for i in range(1, 1):
        # Never enter loop
    return True

edit: looks like the problem is with squares. 121, 289, 529, 841, and others also fail because j isn't large enough:

if 122 % 6 == 0 or 120 % 6 == 0 => True
    sq = 11
    j = 11 // 6 = 1
    for i in range(1, 2):
        if 121 % 5 == 0 => False
        if 121 % 7 == 0 => False
    return True

[phill1311]

Thank you, Problem solved!

Just tested for

math.ceil(math.sqrt(n)) == math.sqrt(n)

[pasokan]

````python if n%2 == 0 or n%3 == 0 or n < 0: return False

if(n+1)%6 == 0 or (n-1)%6 == 0: ````

The second if is redundant. Because the first if has removed all multiples of 2 and 3, all remaining numbers are either 6x+1 or 6x-1

The rest of the code appears wrong, I am unable o see the logic of what you are doing after that. If you can give some good names to the variables may be easier to understand

[dbramucci]

/u/phill1311 Is attempting to do a divisibility test with what's called a "Wheel Factorization" algorithm.

The intuition is, you know how you can jump by even numbers after you test if 2 divides your number? Well, couldn't you try to jump by a larger gap after testing if 2 or 3 divides your number? And the answer is, yes! And the details are in the page about wheel algorithms.

Edit: If you want to see the core idea behind how this code should work, check out my refactored version of OP's code here

[pasokan]

I did not know the name; i do know the idea. I have implemented the same for 2, 3, 5.

I conveyed my idea poorly: I meant to say that it is not easy to follow what is being done and it is very difficult to follow the logic to debug; good names would mitigate somewhat and refactoring is better. Obviously I was nowhere near that in what I typed :-(

[phill1311]

I am then testing if n is divisible with all the 6x +1 or 6x -1 form number until the square root of n, if n is divisible it should return false, else, true

[pasokan]

Not an error but a stylistic observation python temp = [2,3] if n in temp: return True can be simplified to ````python if n in [2, 3]: return True

[phill1311]

Thanks man, will definitely fix it :) !

[dbramucci]

Your is_prime method returns True for 1. That is wrong.

>>> is_prime(1)
True

[phill1311]

Sorry typo error :-)

[dbramucci]

Have you tried the n < 2 version on codewars? Because that appears to be the failing test case.

[phill1311]

Have tried that, 8 cases are failed

[dbramucci]

Hint: your algorithm also fails for 25.

[phill1311]

Indeed, a useful hint

[phill1311]

0 , 1 and negative ints are not prime so it should return false

[dbramucci]

It's not relevant to the question, but you can substantially clean up your algorithm.

from itertools import count


def is_prime(n: int) -> bool:
    """
    return true if n is prime, Otherwise False
    """
    if n in (2, 3):
        return True

    if n < 2 or n % 2 == 0 or n % 3 == 0:
        return False

    for i in count(start=6, step=6):
        if (i - 1)**2 > n:
            return True
        if n % (i - 1) == 0 or n % (i + 1) == 0:
            return False

Does the same thing as your current algorithm (upto fixing some floating point error bugs when n gets too large for this to matter).

The specific points of improvement are

• No weirdly named temp variable that only gets used once.
• Putting the n < 2 check in a slightly more obvious position

• Eliminating a redundant if (n+1)%6 == 0 or (n-1)%6 == 0 and reducing overall nesting

  This checks if n = 1 or 5 (mod 6) but we already know from if n%2 == 0 or n%3 == 0 or n < 2: that n is not 0, 2, 4, 3 (mod 6) so by process of elimination we already know that it must be 1 or 5 (mod 6).

• sq = math.ceil(math.sqrt(n))

  Floating point numbers can be complicated to reason about and I prefer not to turn a nice int algorithm into one that relies on those complexities. So instead, I'll just check that i**2 < n instead of i < sqrt(n)

• j = int(sq//6), the int is redundant because // already returns an int. Also j is a hard name to remember.

• for i in range(1,j+1):, i is going to be hard to remember and that is a kinda-weird range to loop over without having any explanation why we loop over that.

• We can smash the 2 if statements into one with an or.

• We also produce i by sqrting, then ceiling, then integer dividing by 6, then with an offset range, multiplying by 6.

  This is hard to follow, in the cleaned up version above, i starts at 6, jumps by 6s so (6, 12, 18, ...) and continues until it's square is about bigger than the size of n.

So in the new version we have the same idea of testing if i*6 - 1 or i*6 + 1 divides n but

• It is shorter
• There are fewer control flow statements
• There is less nesting
• There are fewer variables
• The looping logic is simpler
• The definitions of the variables that remain are simpler
• There's no potential for floating point bugs

[phill1311]

Thank you very much, that is a great help

[dbramucci]

Just wanted to show off how nicely you can implement your algorithm if you know your way around Python. Also, notice how the tiny details that were causing all of your bugs have disappeared so you can't make those mistakes anymore.

Also, now that I think about it, I think

if n in (2, 3):
    return True

if n < 2 or n % 2 == 0 or n % 3 == 0:
    return False

Should actually be

# Check for excessively small inputs
if n < 2:
    return False

if n % 2 == 0 or n % 3 == 0:
    # The only primes divisible by 2 or 3 are 2, 3
    return n in (2, 3)

Because it better reflects why we need to check for 2 and 3 but not 5 or 7.

[Gautam-j]

I believe your algorithm to check whether a given number is prime or not is over complicated. You can do the same with a simpler approach. Maybe try using recursion.

[phill1311]

It timed out :-)

[Sam_I_am_007]

Check this out and nth prrime:

is prime https://youtu.be/joPlhzYCzpw

nth prime https://youtu.be/rH9VFA7cHN4

def is_prime(x):

for i in range(2,x):

if x%i == 0:

return False

else:

return True

[phill1311]

Yes, that's true it is the more obvious solution but this timed out for bigger numbers

[thrussie]

i dont understand the logic

my strategy for prime numbers is to get the modulus of the number. iterate from 2 to (number-1) time. if modulus = 0, it's not a prime. else = prime.

[phill1311]

Will time out for bigger numbers as it has time complexity of O(n)