Loop identifying primes and non-primes generates false output

Question

I am writing code to identify prime and non-prime numbers in a given list. The idea was to use a nested for loop that iterates through the list and checks it against a number in the range of 2 to n-1, with n being the number to be checked.

Unfortunately the code I come up with, while executing, does not produce the expected output and I seem to be unable to find why.

check_prime = [26, 39, 51, 53, 57, 79, 85]

## write your code here
## HINT: You can use the modulo operator to find a factor

for number in check_prime:
    for x in range (2,number-1):
        if (number %x) ==0:
            print("{} is not a prime because {} is a factor of {}".format(number,x,number))
            break
        elif x  == number-1:
            print ("{} is a prime number".format(number))

I'd expect to get an output for every value with either a prime or non-prime statement, but in reality I only get nonprime statements, and even then they are false:

26 is not a prime because 2 is a factor of 26
39 is not a prime because 3 is a factor of 39
51 is not a prime because 3 is a factor of 51
57 is not a prime because 3 is a factor of 57
85 is not a prime because 5 is a factor of 85

There is obviously an error in my logic, but I can't see it.

yiou could also use a [`for - else`](https://book.pythontips.com/en/latest/for_-_else.html) statement to report 'success'... (and checking any further than `math.sqrt(x)` is not necessary...) — hiro protagonist, Mar 25 '19 at 08:46
"i only get nonprime statements, and even then they are false" -- all of the "not a prime" statements you show appear to be true. What am I missing? — cdlane, Mar 25 '19 at 17:41

Jean-François Fabre · Accepted Answer · 2019-03-25T08:47:37.013

x == number-1 cannot be true because x ranges to number-2 only.

Also, no need to check up to that number, check up to the square root (included) which drastically reduces complexity & computation time in case of huge numbers, and use else statement for inner for loop, no if no break happened, you know that the number is prime:

for number in check_prime:
    for x in range (2,int(number**0.5)+1):
        if number % x ==0:
            print("{} is not a prime because {} is a factor of {}".format(number,x,number))
            break
    else:
        print ("{} is a prime number".format(number))

That fixes your code. You could read more about this classical prime problem: Checking if a number is a prime number in Python

Loop identifying primes and non-primes generates false output

1 Answers1