isPrime function (list + % operator)

Question

I am trying to get a function to determine if N is a prime number. I am new to Python and I know this may not be the most efficient way to solve this but this is my attempt

def is_prime(N):
    k = []                                     #Creates a new list k
    for i in range(2,N):                       #For each i from 2 -> N
        r = N%i                                # r is the remainder of N % i
        k.append(r)                            # appends each remainder r to list k

        if (i == N-1):                         #Once index equals N-1, print list k
            print(k)           

        #For each element j in list k, check if each element in list k is 0
            for j in range (len(k)):        
                if k[j] != 0:             <---PROBLEM
                    return True
                else:
                    return False
print(is_prime(15))

The logic that I have is that when a number is divisible by 1 and itself, and not divisible by any other numbers from 2 to N-1, then it is a prime number. In the code above, I am having trouble comparing the values of each element in list k. I want to determine if the value of each element k[j] == 0. If each element k[j] != 0 and N%1 == 0 and N%N == 0, then it is a prime number!

Any ideas to how I can solve this problem? Please refer to the link below to get a visualization of my code! http://goo.gl/IVIRz7

If you add number divisible in a list why you dont try a condition on `len` list , why you check inside it? — ᴀʀᴍᴀɴ, Jan 19 '16 at 20:49
@Arman I don't quite get what you mean. I'm checking inside the list because I want to know if the value of each element inside it is 0 or not. — misheekoh, Jan 19 '16 at 21:00
@Arman TypeError: 'float' object cannot be interpreted as an integer. I tried adding int(N/2) but that doesn't make sense. — misheekoh, Jan 19 '16 at 21:10
if you want to get more speed have a look at [mine IsPrime implementation in C++](http://stackoverflow.com/a/22477240/2521214) — Spektre, Jan 20 '16 at 08:17

mabe02 · Accepted Answer · 2016-01-19T20:56:05.270

2

I would suggest to solve as follows:

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

This code will work for n >= 2 .

edited Jan 19 '16 at 20:56

answered Jan 19 '16 at 20:53

mabe02

2,676
2
20
35

1

You can do even better by not checking any even values of `i` > 2. – Scott Hunter Jan 19 '16 at 20:54
Could you explain the logic behind using i*i . I think I know why you do it but just wanna hear your opinion. Thanks! – misheekoh Jan 19 '16 at 21:05
@misheekoh: If *ab* == N, then at least one of *a* & *b* must be <= sqrt(N); if *a* <= sqrt(N), then a\*a <= N. – Scott Hunter Jan 19 '16 at 21:10
1

If number `i` is a divisor of `n`, then `n/i` is also a divisor. One of these two divisors is less than or equal to `√ n`. If that were not the case, `n` would be a product of two numbers greater than `√ n`. – mabe02 Jan 19 '16 at 21:11
@scott-hunter if I introduce a check on even numbers,I would increase the time complexity of this code and affect the performance for a large data set, but your suggestion could be an optimization for a small one – mabe02 Jan 19 '16 at 21:14
1

@mabe02: If you make an explicit check for N being even, then initialize `i` to 3 and increment it by 2 each iteration, you (roughly) halve the number of iterations. – Scott Hunter Jan 20 '16 at 01:15

score 2 · Answer 2 · edited Jan 20 '16 at 13:56

2

import math

def is_prime(n):
    i = 3
    while (i <= math.sqrt(n)):
        if (n % i == 0):
            return False
        i += 2
    return True

This is best. Everyone above has mentioned its variation.

edited Jan 20 '16 at 13:56

chepner

497,756
71
530
681

answered Jan 20 '16 at 03:24

sbplex

21
2

score 0 · Answer 3 · answered Jan 20 '16 at 00:35

The above answers will work, but I thought I'd explain your logical error. Your reasoning in English is sound in that if any numbers between [2,N-1] divide N evenly, then you've found a non-prime number.

    for j in range (len(k)):        
        if k[j] != 0:             
            return True
        else:
            return False

What this loop checks is actually if the first number in k is 0 or not. If it is nonzero, the number does not divide N evenly (note this does not mean that the other numbers do divide n evenly), so the number can still possibly be prime, but only if the remainder is nonzero for the remaining potential divisors. In other words, you can return Falseas soon as you see a remainder of 0, but you can only return True only if all divisors have nonzero remainders.

Fixed:

        for j in range (len(k)):        
            if k[j] == 0:
                return False
            return True

The return True statement only executes if we manage to make it all the way through the loop without returning False.

isPrime function (list + % operator)

3 Answers3