Python Prime Search Slower Optimization

Question

I have these 2 version of code. Both are looking for all primes under a certain ceiling value.

The first is testing against the set of all odd numbers. The second in testing against the set of all 6k-1 and 6k+1.

In theory, the second version should be faster than the first. However the result states otherwise.

For under 1 million, the first perform for 1.477835 seconds, while the second perform for 1.521462 seconds.

For under 10 million, the first perform for 30.929565 seconds, while the second perform for 32.825142 seconds.

I have not test these under a different machine.

I could not figure out why I'm getting these results. Because, the second version is suppose to eliminate more composite numbers than the first. However, it perform worse, quite significantly.

I suspect this might be caused by my method of implementation. But even if that were the case, I still wouldn't have the slightest idea of why.

Could it be because of I'm having more nested loops? Or is it to do with memory access? Is it maybe a python's quirk where the implementation details matters? Maybe in some way the first version is simpler and therefore can be easily better optimized by python compared to the second?

If someone could provide some explanations, suggestions, even solutions or alternatives, that would be much appreciated.

#!/usr/bin/env python3.8

import sys
import time
import math

if len(sys.argv) != 2:
    print('usage:')
    print('    (ceiling)')
    print('        Find primes less than ceiling.')
    sys.exit(-1)

try:
    ceiling = int(sys.argv[1])
except:
    print('Fail to parse ceiling ({}) as integer.'.format(sys.argv[1]))
    sys.exit(-2)

if ceiling < 3:
    print('Minimum ceiling value is 3.')
    sys.exit(-3)

prime = [3]

# start benchmark
bench_start = time.perf_counter()

# range(start, end, step) does not include end
# step = 2 to avoid checking even numbers
for i in range(5, ceiling + 1, 2):
    # test only against factors less than the square root
    root = math.sqrt(i)
    for j in prime:
        if j > root:
            prime.append(i)
            break
        if i % j == 0:
            break

# end of benchmark
bench_end = time.perf_counter()

# prepend 2 to the prime list since it was skipped
prime.insert(0, 2)

print(prime)
print('Number of, primes less than {0}, found: {1}'.format(ceiling, len(prime)))

# benchmark report
print('Time elapsed: {:f}s'.format(bench_end - bench_start))

sys.exit(0)

---

#!/usr/bin/env python3.8

import sys
import time
import math

if len(sys.argv) != 2:
    print('usage:')
    print('    (ceiling)')
    print('        Find primes less than or equal to ceiling.')
    sys.exit(-1)

try:
    ceiling = int(sys.argv[1])
except:
    print('Fail to parse ceiling ({}) as integer.'.format(sys.argv[1]))
    sys.exit(-2)

if ceiling < 3:
    print('Minimum ceiling value is 3.')
    sys.exit(-3)

prime = [3]

# start benchmark
bench_start = time.perf_counter()

# range(start, end, step) does not include end
# test only for 6k-1 and 6k+1
# use (ceiling+1)+1 in case of ceiling = 6k-1
for h in range(6, ceiling+2, 6):
    for i in [h-1, h+1]:
        # test only against factors less than the square root
        root = math.sqrt(i)
        for j in prime:
            if j > root:
                prime.append(i)
                break
            if i % j == 0:
                break

# end of benchmark
bench_end = time.perf_counter()

# when ceiling = {6k-1, 6k}, remove 6k+1
if prime[-1] > ceiling:
    prime.pop()

# prepend 2 to the prime list since it was skipped
prime.insert(0, 2)

print(prime)
print('Number of, primes less than or equal to {0}, found: {1}'.format(ceiling, len(prime)))

# benchmark report
print('Time elapsed: {:f}s'.format(bench_end-bench_start))

sys.exit(0)
```

Answer 1

The difference averages to .2 microseconds per number checked.

To see if its the inner loop, try unrolling it in the second program:

...
for i in range(5, ceiling+1, 6):
    # test only against factors less than the square root
    # just use the sqrt of the bigger number to avoid another call to sqrt
    root = math.sqrt(i + 2)

    # tests 6k - 1
    for j in prime:
        if j > root:
            prime.append(i)
            break
        if i % j == 0:
            break

    # tests 6k + 1
    i += 2
    for j in prime:
        if j > root:
            prime.append(i)
            break
        if i % j == 0:
            break
    ...