Code Improvement, Data Science 1

[johnaweiss]

Hi, here's a little optimization for your prime number generator. It's about twice as fast as your original.

The only difference is maxtest, which halves x iterations. We can do this, because for any number n being tested, you only need to test divisors up n/2. You never need to test any multiplier higher than that, but you are.

This change won't improve time for non-primes, because they already stop testing as soon as a divisor is found. It will only halve number of tests on prime numbers.

For student understanding of the concepts you're trying to teach here, this optimization is prolly not necessary.

# my optimized version
import time
t= time.perf_counter()

for n in range(2, 100000):
    maxtest=int(n/2)+1
    for x in range(2, maxtest):
        if n % x == 0:
            print(n, 'equals', x, '*', n//x)
            break
    else:
        print(n, 'is a prime number')

print (time.perf_counter() - t)
out: 79.8 

# your original 
import time
t= time.perf_counter()

for n in range(2, 100000):
    for x in range(2, n):
        if n % x == 0:
            print(n, 'equals', x, '*', n//x)
            break
    else:
        print(n, 'is a prime number')

print (time.perf_counter() - t)
out: 146.7