Distinct primes factors

2015-01-08

Problem 047: Distinct primes factors

Description:

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2 × 2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

Solution:

v
# ... #
. . . .
.  .  .
. . . .
# ... #

>"d"4  *:10p5"d"*:20p*00p230p" ":03p13pv                       >040p030p>>30g1+:30p:10g%\10g/3+g"X"-#v_30g40g:1+40p:10g%\10g/3+p00g30g`#v_v
v                                      <                      _^#`g03g00<^                           <                                  < 0
>"X"30g:10g%\10g/3+p30g>30g+:00g\`       #v_$>30g1+:30p:10g%\10g/3+g" "-|v                                              p+3/g01\%g01:-1g04<
                       ^p+3/g01\%g01:\" ":<  ^                          <>1>:0:40p50p>:40g:10g%\10g/3+g%       #v_40g:10g%\10gv
                                                                           +         |!`\g+3/g01\%g01:p04:+1g04:<p05+1g05/g+3/<
                                                                           4         >$50g4-#v_080p:::4+60p70p3->:70g-  #v_80g1+:80p4-#v_3-.$@
                                                                           ^                 <                  |-g06:+1<              <
                                                                                             ^                 $<        >:0:40p50p>:40g:10g%\10g/3+g%       #v_40g:10g%\10gv
                                                                                                                        ^         <|!`\g+3/g01\%g01:p04:+1g04:<p05+1g05/g+3/<
                                                                                                                                   >$50g4-#v_80g1+80p v
                                                                                                                                  |   -4g08           <
                                                                                                                                  >3-.$@   >080p:70g\`|
                                                                                                                ^                                     <

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

This is a relative straightforward problem:

First we calculate all primes from 0 to 200 000 with a sieve of Eratosthenes.
Then we collect all primes side by side together in the top rows, because we only need to iterate through the primes and never actually do a prime test.
If we iterate through all the primes and test the divisibility we can calculate the number of distinct prime
So we check every fourth number (if it has 4 distinct prime factors).
If we found one, we test the 7 surrounding numbers for 4 adjacent matches (the first one we print out and exit the program)

This program is not that fast, even I did multiple performance improvements:

We pre-calculate the primes with an sieve of Eratosthenes
We generate an easily iterable array of primes
We test only every 4th number - this reduces the number of distinct prime factor calculations greatly
We early exit the "test 7 surrounding numbers" method, when we reached a point where there can't be a positive result

But still, it's mostly optimised brute force and not pretty fast.

Interpreter steps:	3 227 917 351
Execution time (BefunExec):	8min 57s (6.00 MHz)
Program size:	400 x 518
Solution:	134043
Solved at:	2015-01-08