projecteuler/problem5.pl at main · mtompset/projecteuler · GitHub

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#!/bin/perl -Tw

use Data::Dumper;

my @primes;
push @primes, 2;
for my $number (3..20) {
    my $is_prime = 1;
    for my $prime (@primes) {
        if ($number % $prime == 0) {
            $is_prime = 0;
            last;
        }
    }
    if ($is_prime) {
        push @primes, $number;
    }
}

my @all_factors;
for my $number (2..20) {
    my @factors_of_number = factor($number);
    my @check_all_factors = sort { $a <=> $b } @all_factors;
    $#all_factors = -1;
    while (@check_all_factors != 0 || @factors_of_number != 0) {
        if (@check_all_factors == 0) {
            push @all_factors, $factors_of_number[0];
            shift @factors_of_number;
        } elsif (@factors_of_number == 0) {
            push @all_factors, $check_all_factors[0];
            shift @check_all_factors;
        } elsif ($factors_of_number[0] < $check_all_factors[0]) {
            push @all_factors, $factors_of_number[0];
            shift @factors_of_number;
        } elsif ($factors_of_number[0] == $check_all_factors[0]) {
            push @all_factors, $factors_of_number[0];
            shift @factors_of_number;
            shift @check_all_factors;
        } else {
            push @all_factors, $check_all_factors[0];
            shift @check_all_factors;
        }
    }
    print $number, ": ", join ", ", @all_factors, "\n";
}

$result = 1;
for my $value (@all_factors) {
    $result = $result * $value;
}
print "Lowest multiple: $result\n";

sub factor {
    my ($number_to_factor) = @_;

    my @factors;
    for (my $factor = 2;$factor <= $number_to_factor; ++$factor) {
        if ($number_to_factor % $factor == 0) {
            $number_to_factor = $number_to_factor / $factor;
            push @factors, $factor;
            $factor -= 1;
        }
    }
    return @factors;
}