summaryrefslogtreecommitdiffstats
path: root/047.pl
blob: 2f15475901b2ec7b4145d4e21dcc62ae7cb3c3ea (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/perl
use strict;
use warnings;
use integer;
use Math::Prime::XS qw/sieve_primes/;
use List::MoreUtils qw/all uniq/;
use 5.010;

my @primes = sieve_primes(1e6);
my %primes = map { $_, 1 } @primes;
my %factors;

sub factors {
    my ($n_orig) = @_;
    my @ret;
    my $prime_idx = 0;
    my $n = $n_orig;
    while ($n > 1) {
        if (exists $factors{$n}) {
            push @ret, @{ $factors{$n} };
            last;
        }
        if (exists $primes{$n}) {
            push @ret, $n;
            last;
        }
        my $prime = $primes[$prime_idx];
        if (($n / $prime) * $prime == $n) {
            $n /= $prime;
            push @ret, $prime;
        }
        else {
            $prime_idx++;
        }
    }
    $factors{$n_orig} = \@ret;
    return @ret;
}

map { factors($_) } 1..1000000;

for my $n (0..999996) {
    if (all { $_ >= 4 } map { scalar uniq @$_ } @factors{$n..($n + 3)}) {
        print $n + 1, "\n";
        last;
    }
}