check if integer is a prime, if not return smallest factor

Question

I need to check if the given integer is a prime, and return True if so. If not, I need to find the smallest factor which is more than 1. I'm completely new to this and even though code compiles it fails several test cases.

def isPrime(n):
  if (n <= 1) : 
    return n
  if (n <= 3) : 
    return 1

if (n % 2 == 0 or n % 3 == 0) : 
    return 2

i = 5
while(i * i <= n) : 
    if (n % i == 0 or n % (i + 2) == 0) : 
        return i
    i = i + 6

return True

Start over from the definition of what a prime is: A number that only can be divided by 1 and itself. You could try to implement [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat's_little_theorem). — totok, Aug 12 '20 at 10:23
Does this answer your question? [Checking if a number is a prime number in Python](https://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python) — hedy, Aug 12 '20 at 10:25

score 1 · Answer 1 · answered Aug 12 '20 at 10:57

1

A prime is a number that can only be divided by one and itself. So, if we test x, we should test every number y such that 1 < y < x. A good way to test this is to use a for loop. Here is an example:

def isPrime(n):
    for i in range(2,n):
        if n % i == 0:
            return False # because that means that something divides into n perfectly
    return True

There are a few problems with this:

isPrime(1) returns True
Any negative number will return True
The program gets quite a bit slower as the numbers get bigger. For example, it takes 0.145 seconds to complete isPrime(1000003), but primes take longer to process, because as soon as a factor is found, the entire function stops and returns, whereas for a prime to be found, it has to run through every iteration up to n.

I'll leave those problems to you for the moment. In the meantime, we need a way to return the smallest factor. This is actually very easily done:

def isPrime(n):
    for i in range(2,n):
        if n % i == 0:
            return i # i at this iteration is equal to the smallest factor
    return True

So isPrime(20) returns 2, and isPrime(19) returns True. Hopefully this satisfies your needs.

answered Aug 12 '20 at 10:57

monsieuralfonse64

646
6
15

`isPrime(20)` also returns `True`, because 2 evaluates to `True`. – President James K. Polk Aug 12 '20 at 12:20
Are you sure? [Here](https://onlinegdb.com/rJMVJPWzP) is a link to that function online, and it has the output of `2`, which is the lowest factor, excluding 1,of 20. Perhaps you made a formatting error or something when trying to reproduce the above code? Please let me know. – monsieuralfonse64 Aug 12 '20 at 12:25
So you believe that is something is online it must be correct? If you are testing the output of your `isPrime()` method, e.g. `if isPrime(i): print("True")` then both isPrime(20) and isPrime(19) will cause "True" to be printed out. – President James K. Polk Aug 12 '20 at 12:38
1

No I wrote that function online to show you. But I misread your comment, my apologies. Perhaps instead of returning the lowest factor, it should return `False, i`. It is up to the user to decide, depending on what they need the function to do. – monsieuralfonse64 Aug 12 '20 at 12:48
1

Yes, that would be an excellent choice, and maybe `True, None` or `True,0` when it's prime. – President James K. Polk Aug 12 '20 at 12:49

check if integer is a prime, if not return smallest factor

1 Answers1