Distinct primes factors
Problem 047: Distinct primes factors
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?
# ... #
. . . .
. . .
. . . .
# ... #
>"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
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
| -4g08 <
This is a relative straightforward problem:
- First we calculate all primes from
200 000with 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|