Prime number check acts strange

Question

I have been trying to write a program that will take an imputed number, and check and see if it is a prime number. The code that I have made so far works perfectly if the number is in fact a prime number. If the number is not a prime number it acts strange. I was wondering if anyone could tell me what the issue is with the code.

a=2
num=13
while num > a :
  if num%a==0 & a!=num:
    print('not prime')
    a=a+1
  else:
    print('prime')
    a=(num)+1

The result given when 24 is imputed is:

not prime
not prime
not prime
prime

How would I fix the error with the reporting prime on every odd and not prime for every even?

Answer 1

You need to stop iterating once you know a number isn't prime. Add a break once you find prime to exit the while loop.

Making only minimal changes to your code to make it work:

a=2
num=13
while num > a :
  if num%a==0 & a!=num:
    print('not prime')
    break
  i += 1
else: # loop not exited via break
  print('prime')

Your algorithm is equivalent to:

for a in range(a, num):
    if a % num == 0:
        print('not prime')
        break
else: # loop not exited via break
    print('prime')

If you throw it into a function you can dispense with break and for-else:

def is_prime(n):
    for i in range(3, n):
        if n % i == 0:
            return False
    return True

Even if you are going to brute-force for prime like this you only need to iterate up to the square root of n. Also, you can skip testing the even numbers after two.

With these suggestions:

import math
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

Note that this code does not properly handle 0, 1, and negative numbers.

We make this simpler by using all with a generator expression to replace the for-loop.

import math
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

Answer 2

def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2: 
        return True    

    # all other even numbers are not primes
    if not n & 1: 
        return False

    # range starts with 3 and only needs to go up 
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True

Taken from:

http://www.daniweb.com/software-development/python/code/216880/check-if-a-number-is-a-prime-number-python

Answer 3

def is_prime(n):
    return all(n%j for j in xrange(2, int(n**0.5)+1)) and n>1

Answer 4

The two main problems with your code are:

1. After designating a number not prime, you continue to check the rest of the divisors even though you already know it is not prime, which can lead to it printing "prime" after printing "not prime". Hint: use the `break' statement.
2. You designate a number prime before you have checked all the divisors you need to check, because you are printing "prime" inside the loop. So you get "prime" multiple times, once for each divisor that doesn't go evenly into the number being tested. Hint: use an else clause with the loop to print "prime" only if the loop exits without breaking.

A couple pretty significant inefficiencies:

1. You should keep track of the numbers you have already found that are prime and only divide by those. Why divide by 4 when you have already divided by 2? If a number is divisible by 4 it is also divisible by 2, so you would have already caught it and there is no need to divide by 4.
2. You need only to test up to the square root of the number being tested because any factor larger than that would need to be multiplied with a number smaller than that, and that would already have been tested by the time you get to the larger one.

Answer 5

This example is use reduce(), but slow it:

def makepnl(pnl, n):
    for p in pnl:
        if n % p == 0:
            return pnl
    pnl.append(n)
    return pnl

def isprime(n):
    return True if n == reduce(makepnl, range(3, n + 1, 2), [2])[-1] else False

for i in range(20):
    print i, isprime(i)

It use Sieve Of Atkin, faster than above:

def atkin(limit):
    if limit > 2:
        yield 2
    if limit > 3:
        yield 3

    import math
    is_prime = [False] * (limit + 1)

    for x in range(1,int(math.sqrt(limit))+1):
        for y in range(1,int(math.sqrt(limit))+1):
            n = 4*x**2 + y**2

            if n<=limit and (n%12==1 or n%12==5):
                # print "1st if"                                                                                                                    
                is_prime[n] = not is_prime[n]
            n = 3*x**2+y**2
            if n<= limit and n%12==7:
                # print "Second if"                                                                                                                 
                is_prime[n] = not is_prime[n]
            n = 3*x**2 - y**2
            if x>y and n<=limit and n%12==11:
                # print "third if"                                                                                                                  
                is_prime[n] = not is_prime[n]

    for n in range(5,int(math.sqrt(limit))):
        if is_prime[n]:
            for k in range(n**2,limit+1,n**2):
                is_prime[k] = False

    for n in range(5,limit):
        if is_prime[n]: yield n

def isprime(n):
    r = list(atkin(n+1))
    if not r: return False
    return True if n == r[-1] else False

for i in range(20):
    print i, isprime(i)

Answer 6

Your problem is that the loop continues to run even thought you've "made up your mind" already. You should add the line break after a=a+1

Answer 7

After you determine that a number is composite (not prime), your work is done. You can exit the loop with break.

while num > a :
  if num%a==0 & a!=num:
    print('not prime')
    break          # not going to update a, going to quit instead
  else:
    print('prime')
    a=(num)+1

Also, you might try and become more familiar with some constructs in Python. Your loop can be shortened to a one-liner that still reads well in my opinion.

any(num % a == 0 for a in range(2, num))

Answer 8

Begginer here, so please let me know if I am way of, but I'd do it like this:

def prime(n):
    count = 0
    for i in range(1, (n+1)): 
         if n % i == 0: 
             count += 1
    if count > 2:
        print "Not a prime"
    else:
        print "A prime"

Answer 9

This would do the job:

number=int(raw_input("Enter a number to see if its prime:"))
if number <= 1:
    print "number is not prime"
else:
    a=2
    check = True
    while a != number:
        if number%a == 0:
            print "Number is not prime"
            check = False
            break
        a+=1
    if check == True:
        print "Number is prime" 

Answer 10

a=input("Enter number:")

def isprime(): 

    total=0
    factors=(1,a)# The only factors of a number
    pfactors=range(1,a+1) #considering all possible factors


    if a==1 or a==0:# One and Zero are not prime numbers
        print "%d is NOT prime"%a


    elif a==2: # Two is the only even prime number
        print "%d is  prime"%a


    elif a%2==0:#Any even number is not prime except two
        print "%d is NOT prime"%a  



    else:#a number is prime if its multiples are 1 and itself 
         #The sum of the number that return zero moduli should be equal to the "only" factors
        for number in pfactors: 
            if (a%number)==0: 
                total+=number
        if total!=sum(factors):
            print "%d is NOT prime"%a 
        else:
             print "%d is  prime"%a
isprime()

Answer 11

This is a slight variation in that it keeps track of the factors.

def prime(a):
    list=[]
    x=2
    b=True

    while x<a:
        if a%x==0:
            b=False
            list.append(x)
        x+=1

    if b==False:
        print "Not Prime"
        print list
    else:
        print "Prime"

Answer 12

Prime number check.

def is_prime(x):
    if x < 2:
        return False
    else:
        if x == 2:
            return True
        else:
            for i in range(2, x):
                if x % i == 0:
                    return False
            return True
x = int(raw_input("enter a prime number"))
print is_prime(x)

Answer 13

max=int(input("Find primes upto what numbers?"))
primeList=[]
for x in range(2,max+1):
    isPrime=True
    for y in range(2,int(x**0.5)+1) :
        if x%y==0:
            isPrime=False
            break

    if isPrime:
        primeList.append(x)
print(primeList)

Answer 14

# is digit prime? we will see (Coder: Chikak)

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