CODEWITHSUNDEEP
python
Irulenot
Irulenot

Reputation: 1

Part of this prime number program is just not making sense to me

Could someone explain 

for k in range(2, 1+int(sqrt(i+1))):

to me? I am having a hard time comprehending how

1+int(sqrt(i+1)

truly works.

I understand 1 is being added to i, and it is being square rooted, and it must be an integer. But I don't comprehend how that achieves the goal of the whole program

from math import sqrt

count = 1
i = 1
while count < 1000:
    i += 2
    for k in range(2, 1+int(sqrt(i+1))):
        if i%k == 0:       
            break
    else:
        # print(i) ,
        count += 1
        # if count%20==0: print ""
print i

whose goal is to find the 1000th prime.

Upvotes: 0

Views: 75

Answers (1)

Patashu
Patashu

Reputation: 21783

If a number is to be tested for primality, it is sufficient to test all factors up to sqrt(number), because any factor above sqrt(number) has a corresponding factor below sqrt(number).

e.g. if you want to test if 36 is prime, it is sufficient to test up to 6 - for example, 12 is a factor of 36, but its other factor is 3, which you already tested by then.

Upvotes: 6

Related Questions