prime numbers

[astral_travel]

i wrote this code:

user_input = int(input("choose a number: "))

a = range(2, user_input-1)

for x in a:
    if user_input % x == 0:
        print(f"number is not prime, divides by {x}")
    else:
        print("number is prime")

the output is this:

Output:
choose a number: number is not prime, devides by 2
number is not prime, devides by 3
number is prime
number is not prime, devides by 5
number is not prime, devides by 6
number is prime
number is prime
number is prime
number is not prime, devides by 10
number is prime
number is prime
number is prime
number is prime
number is not prime, devides by 15
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime
number is prime

Process finished with exit code 0

now, the part that it is writing all of the numbers that divides the number that is not prime - that's good.
but the problem is it's writing also "number is prime" numerous times ...(when it shouldn't even write it once - if the code was correctly written).

i know it does this because it runs x through a in the for loop, but how do i isolate the output to be one of the two ?

[deanhystad]

A number is prime if it is divisible by no number other than 1 and itself. You are only testing if it is divisible by 2 before you give up and say it is prime. You should stop testing when you find a factor and then report the number is not prime. You should not say a number is prime until you have tested all possible factors.

Your test is inefficient. You test if 11 is divisible by 2, 4 and 8. All even numbers are divisible by 2, there is no reason to test any other even factor.

Your test is inefficient. What is the largest possible factor of a non-prime number? Is it number-1? Do you have to test if 10 divides evenly into 11?

[astral_travel]

okay, i guess i can divide the user_input in 2 and have it rounded down (in case it's something like 15.5), and have that as the largest factor that it can be divided into...

well, if i understand it correctly - what you're implying is having a recursion ? so the result will be expressed only after the whole list of possibilities has been taken into account ?

i'm a little lost...

addition - that's what i'm saying - it's enough for a number to be an even number to not be a prime number, isn't it so ?

[astral_travel]

okay, 2 is also a prime number - but i can exclude it with some if statement of its own..no ?

[deanhystad]

You can take the square root of a number and round down. Test up to that and you have tested all possible factors. To determine if 101 is prime you only need to test 2, 3, 5 and 7. You can test 9 too, but it is redundant. Every non-prime number is a product of primes.

No recursion is required to test for prime. Nor is it a good idea. Recursion is a bad fit for this problem.

And stop doing this:

a = range(2, user_input-1)
 
for x in a:

Unless your loop range is going to change, put the range in the for expression so I don't have to hunt it down.

for x in range(2, user_input-1):

In addition to not performing the test correctly, you missed some special cases in your OP. 2 is a prime number and it is the smallest prime number. 0 and 1 are not prime, but they would pass as prime using your test. 2 is prime, and it would be reported as not prime by your test.

[astral_travel]

okay, what is the relation (in the example you have given) between 101 and 2, 3, 5, 7 and possibly 9 (and why is it redundant) ?

and, suppose i have a root which is 5.656854249492381 (square root of 32) - do i round it down to 5 ? and what is the meaning of this 5 ?

okay, (this is an addition), i just found this on google:

So, if you test all the numbers up to the square root, you can rest assured that the number is prime. For example, the square root of 23 is around 4.8, so you would test 23 to see if it can be divided by 2, 3 or 4. It cannot be, so 23 is prime.

but why does it work like this ?

thanks

[astral_travel]

i need some help here, i know it looks silly - i just don't know what to do.
here's the code i tried so far:

import math

user_input = int(input("choose a number: "))

a = math.floor(math.sqrt(user_input))

print("square root of user input is: ", a)

for x in range(2, a):
    if x % a != 0:
        print("this is a prime number")
    else:
        print("this is not a prime number")

[deanhystad]

This is best described using an example. Lets say we want to determine if 36 is prime. It is not, really not. 36 has a lot of factors.
2 x 18
3 x 12
4 x 9
6 x 6 <- square root of 36
9 x 4
12 x 3
18 x 2

Notice that the factors below the square root are just swapped versions of factors above the square root. This is because of the Commutative property of multiplication which says "a x b = b x a". If we were testing for prime, we wouldn't have to test 18, because we already tested for 18 when we tested for 2. We don't have to test 13, because we already tested 13 when we tested 3. The largest number we ever have to test to determine if a number is prime is the square root of the number. Any potential factor greater than the square root has already been tested by the commutative property. Now apply this information to determining if 101 is prime.

To determine if 101 is prime, the largest potential factor we need to test is the square root of 101, 10.05. Round down to 10. Without any kind of optimization, we might test for prime using 2, 3, 4, 5, 6, 7, 8, 9, 10. This is already far better than testing 2 - 100 as potential factors, 10 times fewer divisions. But we can do even better than that.

We can factor some of the remaining potential factors
2
3
4 = 2 x 2
5
6 = 2 x 3
7
8 = 2 x 2 x 2
9 = 3 x 3
10 = 2 x 5

If a number is divisible by 4, 6, 8 or 10 (or any even number) it is also divisible by 2. Thus, any number that has an even factor also has 2 as a factor. This means the only even factor we ever have to test is 2. This cuts the list of potential factors almost in half; 2, 3, 5, 7, 9.

You probably also noticed that 9 can be factored to 3 x 3. For the same reason that any number that is a multiple of 2 (any even number) can be ignored as a potential factor, any number that is a multiple of 3 (or 5 or 7 or any of the other primes) can be ignored as a factor. There is no reason to test if 9 is a factor if you already ruled out that 3 is not a factor. However, it is not as easy to rule out multiples of primes as it is multiples of 2, so we will test if 101 is divisible by 9 and ignore that it is not optimal.

An algorithm to determine if a number is prime must:
1. Have a special test for 2, the only even prime number
2. Have a special test for numbers less than 2, all of which are not prime.
3. Only if the number > 2, test for prime using modulo and factors
a. If the number is divisible by a factor it is not prime.
b. If you tested all factors the number is prime

Step 3 is easily optimized to only test odd factors (read about the range() function).

[deanhystad]

import math  # Don't need floor
 
user_input = int(input("choose a number: "))
 
a = math.floor(math.sqrt(user_input))  # This does not convert value to int.  use int()
 
print("square root of user input is: ", a)
 
# This code is a test for odd/even, not a test for prime/not prime
for x in range(2, a):  # This tests even numbers as well as odd.  Not error, but inefficient
    if x % a != 0: 
        print("this is a prime number")  # Cannot say a number is prime until you test all factors
    else:
        print("this is not a prime number")

[astral_travel]

what about this (code) ?
it works just fine - but when you input 1 as a number to check - it gives "number is prime" even though i wrote at the end

elif user_input < 2:
    print("this number is not prime")

the code:

import sys

user_input = int(input("choose a number: "))

if user_input > 0:
    for x in range(2, user_input-1):
        if user_input % x != 0:
            continue
        elif user_input % x == 0:
            sys.exit("number is not prime")
    print("number is prime")
elif user_input == 2:
    print("the number is prime")
elif user_input < 2:
    print("this number is not prime")

and also i used sys.exit() - otherwise it gives a problematic output...(if i just use print()

thoughts ?