cancel
Showing results for
Did you mean:

## Q For Problems - Episode 7  Contributor

Hi everyone,

Please check out episode 7 of the Q For Problems video series.

This covers problem 7 from the Project Euler problem set.

Project Euler - Problem 7

The problem is to find the 10 001st prime number.

Feel free to share your own solutions and ideas in the comments.

Github Repo

Thanks   Moderator

Brilliant episode 👏

Great work, thanks for sharing @jkane17  Valued Contributor

Another strategy: use Eratosthenes’ Sieve to write `pt` to return the primes to `x`. (No iterated arithmetic, but hungry for space.)

1. Use the π function `{x%log x}` to find a number P with N or more primes below it.
2. `@[;n] pt (n>pi::)(2*)/1000`

Details on GitHub at qbists/studyq/euler/07.md  Valued Contributor

Inserting a line at the beginning of the Cond in your `.math.isPrimes` will let it take the vector argument you give it:

``0<type x; .z.s each x;``

Your 6K strategy is to run through every 6th number and test one before and one behind. Since you’re looking (only) for the 10,001st prime, you should be able to save space by keeping in your state the last pair tested, the result, and the count of primes seen so far – we don’t need a list of 10,000 primes.

``````nprimes4:{[N]                                     / Nth prime
is:("i"\$1,count::;.math.isPrime;::)@\:2 3;      /   initial state: k:1; 2 3 found
step:{[x;y;z]
b:.math.isPrime n:-1 1+6*first x;             /     test 2 candidates
(x+1,sum b;b;n)                               /     new state
}.;
fs:{x>y . 0 1}[N;] step/is;                     /   final state
{[n;kc;b;p] (p where b)@(kc 1)-n}[N;;;] . fs }
``````

Which is what we find.

``````q)\ts nprimes3 10001
371 262784
q)\ts nprimes4 10001
370 5248

q)\ts nprimes3 100001
13434 2097792
q)\ts nprimes4 100001
12290 17536``````

Either the time we saved by not appending to the list of primes 5000+ times was lost to extra code – or the interpreter was smart enough to do the appending without 5000+ internal copies.

It’s instructive to compare with space-hungry Eratosthenes, which instead of arithmetic uses long vector ANDs.

``````np:{[N]                                           / Nth prime
es:{                                            /   Eratosthenes' sieve
is:{(1#2;0b,1_x#10b)};                        /     initial state
step:{(x,n;y&count[y]#i<>til n:1+i:y?1b)}. ;  /     step: sieve next prime
{x>last first y}[floor sqrt x] step/is x };
rslv:raze @[;1;1+where@]::;                     /   resolve result
pt:rslv es::;                                   /   primes to
pi:{x%log x};                                   /   π(x) first approximation
@[;n]pt (N>pi@)(2*)/1000 }
``````

Not intuitively obvious which will run faster. But it turns out vector-hungry q loves long vectors and implicit iteration.

``````q)\ts np 10001
1 526192
q)\ts np 100001
43 8391536
``````

It’s a good example of how in a vector language ‘overcomputing’ (Eratosthenes returns all the primes found) can still be orders of magnitude faster.

Contributors