(29C) Prime numbers up to 10'000

[Thomas Klemm]

I wondered how much better using A007310 and primes instead of odd numbers would be.

The most expensive operation is probably checking if n is divisible by a probe π.
Thus I counted how often that happens.

n ∈ A007310 and π ∈ primes

This is essentially the algorithm of my program from above:

Code:

primes = [ 5,  7, 11, 13, 17, 19, 23, 29,
          31, 37, 41, 43, 47, 53, 59, 61,
          67, 71, 73, 79, 83, 89, 97, 101 ]

N = 10000
n = 5
Δn = 2
count = 0

while n < N:
    for π in primes:
        if n < π**2:
            print(n)
            break
        count += 1
        if n % π == 0:
            break
    n += Δn
    Δn = 6 - Δn

print(count)

count = 28760

---

both n and π are odd numbers

This is the algorithm used by Jürgen:

Code:

N = 10000
n = 5
Δn = 2
count = 0

while n < N:
    for π in range(3, 102, Δn):
        if n < π**2:
            print(n)
            break
        count += 1
        if n % π == 0:
            break
    n += Δn

print(count)

count = 55958


That is more by a factor of 1.9456.

---

We can now gradually improve the algorithm and keep track of the changes.

n ∈ A007310 and π is odd

Code:

N = 10000
n = 5
Δn = 2
count = 0

while n < N:
    for π in range(5, 102, Δn):
        if n < π**2:
            print(n)
            break
        count += 1
        if n % π == 0:
            break
    n += Δn
    Δn = 6 - Δn

print(count)

count = 43625

---

n is odd and π ∈ {3} ∪ A007310

Code:

A007310 = [  5,  7, 11, 13, 17, 19, 23, 25, 29, 31, 35,
            37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67,
            71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101 ]

N = 10000
n = 5
Δn = 2
count = 0

while n < N:
    for π in [ 3 ] + A007310:
        if n < π**2:
            print(n)
            break
        count += 1
        if n % π == 0:
            break
    n += Δn

print(count)

count = 40350

---

both n and π are ∈ A007310

Code:

A007310 = [  5,  7, 11, 13, 17, 19, 23, 25, 29, 31, 35,
            37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67,
            71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101 ]

N = 10000
n = 5
Δn = 2
count = 0

while n < N:
    for π in A007310:
        if n < π**2:
            print(n)
            break
        count += 1
        if n % π == 0:
            break
    n += Δn
    Δn = 6 - Δn

print(count)

count = 35354


This is better by a factor 1.5827 compared to the original program.
And that's close to 3 ÷ 2 = 1.5 what I would have expected.

However just using primes as probes is still better by a factor of 1.2292.
That's probably since in the worst case of n being a prime all probes have to be checked.
The length of primes is 27 and that of A007310 is 33.
This gives a factor of 1.2222.

Cheers
Thomas