Project Euler #7: 10,001st prime

Community Support
1

https://projecteuler.net/problem=7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10,001st prime number?

Solution 1

Use Eratosthenes’ Sieve to generate enough primes. Then pick the 10,001st.

The Sieve: start with an initial state of known primes (2) and a vector flagging the (odd) numbers still to test.

Here it is in slo-mo.

 

And in code:

q)kc:{(1#2;0b,1\_x#10b)}/ (known primes; flag candidates)q)kc20,200101010101010101010b

The step function: sieve the next prime. It’s the first number flagged. Join it to the known primes and remove its multiples from the flag vector.

q)snp:{(x,n;y&count[y]#i<>tiln:1+i:y?1b)}./ sieve next primeq)snpkc202300001010001010001010b

Sieve the initial state to get all the primes under a million. (Surely enough?)

q)es:{{x>lastfirsty}[floorsqrtx]snp/kcx}/ Eratosthenes' Sieveq)es50235700000000001010001010001000001010000010001010001000bq)rslv:raze@[;1;1+where@]@/ resolve resultq)rslves5023571113171923293137414347q)pt:rslves@/ primes toq)pt5023571113171923293137414347

Solution 2

The While form of the Over iterator here uses a test function that stops when candidates exceed the square rot of N. All the remaining flags then mark primes, and we know that we have sieved out all the primes below N.

But until then we do not know how many of the remaining flags mark primes. The first item of the state lists the primes we have found.

If we examine the intermediate result of sieving for primes below a million, we see there have been 168 iterations.

q)countfirstes1000000/ # iterations169

Sieving for primes below a million was a lucky guess. Is there a lower N we could use?

By convention ?(x) denotes the number of primes below x. Its values have been calculated for powers of 10.

PI:04251681229959278498664579576145550487534455052511411805481337607912018346065536839

This tells us that to get 10,001 primes the lowest power of 10 to use for N is 106.

q)sumPI<100016iq)countpt"j"$10xexpsumPI<1000178498

We have replaced a lucky guess with a reasoned approximation. But it’s still the same number of iterations, and seven times as many primes as we need.

Solution 3

The Prime Number Theorem tells us that

?(x)?x÷ln?(x)

What value of x gives us ?(x)>10000?

Let’s look. Start with 1000 and, instead of going up in orders of magnitude, keep doubling.

pi:{x%logx}/ ?(x) first approximationq)(10000>pi@)(2*)/1000128000q)pi12800010884.55q)countpt(10000>pi@)(2*)/100011987

We could refine the search to find a lower value of N but it is unlikely to reduce the number of iterations by much.

q)countfirstes128000/ # iterations72

Comments

This is a nice example of using q in the REPL not only to find a solution but to explore how to improve it.

kc:{(1#2;0b,1\_x#10b)}/ (known primes; flag candidates)snp:{(x,n;y&count[y]#i<>tiln:1+i:y?1b)}./ sieve next primees:{{x>lastfirsty}[floorsqrtx]snp/kcx}/ Eratosthenes' Sieverslv:raze@[;1;1+where@]@/ resolve resultpt:rslves@/ primes topi:{x%logx}/ ?(x) first approximationp:pt(10000>pi@)(2*)/1000/ first 10000 or so primesp@10000/ 10001st prime

Contributors

  • Stephen Taylor

from https://github.com/qbists/studyq/blob/main/euler/07.md

2

Nicely done, @SJT 

Great content!