I have 2 codes in Python that use to find prime number. Why do in these 2 codes, one produces results much faster than other

Question

I have written program to find prime numbers, use as much technique as I can to find prime numbers. However, when searching the Internet (on GeekforGeek), I found one that kinda similar to mine (same on algorithm ideas), but produce the same result much faster. I wonder what is the difference between the two

We both reduce the test by 1) only check the odd numbers. 2) have the divisor only at odd numbers 3) only allow divisor to reach square root of that number

#my code
import time
import math
start = time.time()
upperlimit = 1000000 
counter = 1
number = 3
while number<upperlimit: #loop to check number
    shittyvalue = 0
    division = 3
    while math.sqrt(number) >= division: # conditional loop
        if number % division == 0:
            shittyvalue = 1 #for giving the annoucement on whether this number is a prime
            break
        division = division + 2
    if shittyvalue == 0:
        counter = counter + 1
    number = number + 2
print ("There are ",counter, " prime numbers")
end = time.time()
print ("Found in ",end-start, " seconds")

#GeekforGeek code's
# Python Program to find prime numbers in a range 
import math 
import time 

def is_prime(n): 
    if n <= 1: 
        return False
    if n == 2: 
        return True
    if n > 2 and n % 2 == 0: 
        return False
    max_div = math.floor(math.sqrt(n)) 
    for i in range(3, 1 + max_div, 2): 
        if n % i == 0: 
            return False
    return True

# Driver function 
t0 = time.time() 
c = 0 #for counting 

for n in range(1,1000000): 
    x = is_prime(n) 
    c += x 
print("Total prime numbers in range :", c) 

t1 = time.time() 
print("Time required :", t1 - t0)

The result shown:

Mine: There are 78498 prime numbers Found in 17.29092025756836 seconds

GeekforGeek's: Total prime numbers in range : 78498 Time required : 3.9572863578796387

One obvious difference: the first version calculates a square root on each iteration of the inner loop, the second version calculates it only once per number being tested. — jasonharper, Sep 16 '19 at 13:40
See if this helps https://stackoverflow.com/questions/1801391/how-to-create-the-most-compact-mapping-n-%e2%86%92-isprimen-up-to-a-limit-n/71438297#71438297 — Gary, Mar 11 '22 at 12:13
Please check this if this helps. This may suit your speed needs. This is probably the best. https://stackoverflow.com/a/71438297/3204942 — Gary, Mar 11 '22 at 12:17

Abhishek Katwa · Answer 1 · 2019-09-16T14:05:42.960

2

You can take Math.sqrt(number) out of the while loop. It is a heavy operation when n is large.

For loops are faster than while loops in Python Why is looping over range() in Python faster than using a while loop?

edited Sep 16 '19 at 14:05

answered Sep 16 '19 at 13:52

Abhishek Katwa

19
2

score 1 · Answer 2 · answered Sep 16 '19 at 13:58

There are two primary reasons.

1) math.sqrt(number) is executed repeatedly.

2) while vs for:

import time

upper_limit = 1000000


def test_while_loop():
    start = time.time()

    sum = 0

    idx = 0
    while idx < upper_limit:
        sum += idx
        idx += 2

    end = time.time()

    print("Found in", end - start, " seconds")
    print("Sum", sum)


test_while_loop()


def test_for_loop():
    start = time.time()

    sum = 0

    for idx in range(0, upper_limit, 2):
        sum += idx

    end = time.time()

    print ("Found in", end - start, " seconds")
    print("Sum", sum)


test_for_loop()

Output (will be different on each run, but try to observe the difference):

Found in 0.0648810863494873  seconds
Sum 249999500000
Found in 0.02890491485595703  seconds
Sum 249999500000

I have 2 codes in Python that use to find prime number. Why do in these 2 codes, one produces results much faster than other

2 Answers2