Prime number detector

[Mark17]

This is not printing what I expect so hopefully someone can point out what I'm not understanding.

for i in range(2,101): #prime number detector
    for j in range(2, 1 + int(round(i/2, 0))):
        print(f'(i , j) is ({i},{j})') 
        #print('i is ', i)
        #print('j is ', j)
        if i % j == 0:
            print(i/j)
            decision = 'composite'
            continue
        else: continue

The idea is to have the program test numbers 2-100 inclusive. Into each number, I want to divide 2 through the first integer greater than 50% of the number in question (over half and we know the result is going to be between 1-2, which amounts to a nonzero modulus). What the program is looking for is a zero modulus because that means another integer factor exists besides the number itself and 1.

Ultimately, the program gets this right:

Output:
Prime numbers under 100 are:  [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97].

However, I don't understand why some loop pairings don't get printed. The first 32 lines of output are as follows:

Output:
(i , j) is (3,2)
(i , j) is (4,2)
2.0
(i , j) is (5,2)
(i , j) is (6,2)
3.0
(i , j) is (6,3)
2.0
(i , j) is (7,2)
(i , j) is (7,3)
(i , j) is (7,4)
(i , j) is (8,2)
4.0
(i , j) is (8,3)
(i , j) is (8,4)
2.0
(i , j) is (9,2)
(i , j) is (9,3)
3.0
(i , j) is (9,4)
(i , j) is (10,2)
5.0
(i , j) is (10,3)
(i , j) is (10,4)
(i , j) is (10,5)
2.0
(i , j) is (11,2)
(i , j) is (11,3)
(i , j) is (11,4)
(i , j) is (11,5)
(i , j) is (11,6)
(i , j) is (12,2)

I would expect this to begin with i = 2. Then, L2 becomes j in range (2, 1 + int(rnd(1,0)) or (2,2) so it will do nothing since the start is actually beyond the exclusive ending point. This is consistent with the output.

Next, i = 3. L2 is then range(2, 1 + int(rnd(1.5, 0))) or range(2, 3). This should proceed only for j = 2. That is consistent with the output.

Next, i = 4. L2 is then range(2, 1 + int(rnd(2, 0))) or range(2, 3). This should proceed only for j = 2. That is consistent with the output.

Next, i = 5. L2 is then range(2, 1 + int(rnd(2.5, 0))) or range(2, 4). This should proceed for j = 2 and j = 3. Why does only (5,2) print out for i = 5?

Next, i = 6. L2 is then range(2, 1 + int(rnd(3, 0))) or range(2, 4). This should proceed for j = 2 and j = 3. That is consistent with output.

Next, i = 7. L2 is then range(2, 1 + int(rnd(3.5, 0))) or range(2, 5). This should proceed for j = 2, j = 3, and j = 4. That is consistent with output.

Next, i = 8. L2 is then range(2, 1 + int(rnd(4, 0))) or range(2, 5). This should proceed for j = 2, j = 3, and j = 4. That is consistent with output.

Next, i = 9. L2 is then range(2, 1 + int(rnd(4.5, 0))) or range(2, 6). This should proceed for j = 2, 3, 4, and 5. Where is (9, 5)?

i = 10, 11, and 12 are consistent with output.

Next, i = 13 (not shown). L2 is then range(2, 1 + int(rnd(6.5, 0))) or range(2, 8). This proceeds for j = 2, 3, 4, 5, and 6 but (13, 7) never prints. Why?

Thanks!

[deanhystad]

Did you read the documentation before using round?

https://docs.python.org/3/library/functions.html#round

if two multiples are equally close, rounding is done toward the even choice (so, for example, both round(0.5) and round(-0.5) are 0, and round(1.5) is 2)

So 2.5 is round to 2, not 3. This is probably the reason for the inconsistencies you are seeing.

Round is not the correct choice here. Just use int(). Divide isn't the right choice either. Your algorithm works because you are testing all possible factors. You are also testing a lot of potential factors you don't need to test. You can stop testing when j >= i**0.5.

count = 0
for i in range(2, 101):
    for j in range(2, 1 + int(round(i / 2, 0))):
        count += 1
        if i % j == 0:
            break
print("Divisions =", count)

Output:
Divisions = 629

count = 0
for i in range(3, 101, 2):
    for j in range(3, int(i**0.5), 2):
        count += 1
        if i % j == 0:
            break
print("Divisions =", count)

Output:
Divisions = 72

Any non-prime number is the product of primes. This allows testing even fewer factors. For 97 you only need to test 2, 3, 5, 7. For 997 you need to additionally test 11, 13, 17, 19, 23, 29, 31. There is a neat algorithm called the Sieve of Eratosthenes that fits perfectly with what you are doing. You should take a look, not so much to find primes (there is a python call for that), but to see how changing your approach to a problem can result in vast improvements. Solving a problem where you want to determine if a number has any factors in a way that doesn't do division. Brilliant!

[jefsummers]

Integers and rounding.
For 5,2, see here -

Output:
Python 3.11.5 (tags/v3.11.5:cce6ba9, Aug 24 2023, 14:38:34) [MSC v.1936 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
print(5/2)
2.5
print(int(round(5/2,0)))
2

So it won't go up to 3, other problems are similar.

[jefsummers]

Integers and rounding.
For 5,2, see here -

Output:
Python 3.11.5 (tags/v3.11.5:cce6ba9, Aug 24 2023, 14:38:34) [MSC v.1936 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
print(5/2)
2.5
print(int(round(5/2,0)))
2

So it won't go up to 3, other problems are similar.

[Mark17]

Did you read the documentation before using round?

I did not... just assumed rounding was "normal," mathematical rounding. I guess anytime things don't work out as I suspect I should look to check documentation.

Good stuff here. Thanks!

[deanhystad]

What is "normal"? On a computer it is unlikely that you will ever get a float that that is halfway between two integers. Depending on the result of rounding numbers near midpoint is like depending on comparing floats for equality. Both are completely predictable while being very difficult to predict. You have to be really careful when using floats in comparisons.