Script to detect prime numbers in Python

Question

I decided to create a script to detect prime numbers, but in order to really understand what I’m doing I created something from scratch, something I thought.

At first my program worked, but I noticed that it "hangs" in large numbers, above 5 digits, as if it were consuming all the memory of the PC, after a while it unlocks and finally shows the result, I don’t know if this is normal. Finally, I would like to improve this code, in order to understand in a very didactic way what I am doing, if possible, someone who can help me visualize the reason for the "lock", and its correction. Follows:

numero = int(input('Digite um numero:'))

div = 0

cont = numero

while cont >= 1:

    if numero % cont == 0:

    div += 1

     cont += -1

if div < 2 or div > 2:

    print('Não é primo!')

elif div == 2:

    print('É primo')

Another solution I thought was this, but it hangs the same way:

numero = int(input('Digite um numero:'))

div = 0

cont = numero

while div < 2:

    if numero % cont == 0:

     div += 1

     cont += -1

if div < 2 or div > 2:

    print('Não é primo!')

elif div == 2:

     print('É primo')

I’m sorry, I still can’t post codes correctly on this site, I hope you can see the identations...

Answer 1

It is normal for it to take too long with very large numbers, if you put the number 1000 per exeplo that means it will be 1000 divisions and over a thousand comparisons with the if... you could improve the performance by dividing this number only by the numbers that go up to half of it, thousand for example there is no splitter greater than 500 that is your half... then you could improve the performance by 50% since it would be necessary to make only half of the calculations and comparisons in the loop