123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # License: GPLv3
- # Date: 04 May 2017
- # https://github.com/trizen
- # https://projecteuler.net/problem=516
- # Runtime: 41.831s.
- use 5.010;
- use strict;
- use ntheory qw(
- factor
- euler_phi
- is_prime
- );
- my @smooth = (1);
- my $limit = 1e12;
- my $mod = 1 << 32;
- foreach my $p (2, 3, 5) {
- foreach my $n (@smooth) {
- if ($n * $p <= $limit) {
- push @smooth, $n * $p;
- }
- }
- }
- @smooth =
- sort { $b <=> $a }
- grep { is_prime($_) }
- map { $_ + 1 } @smooth;
- my @h = (1);
- my $sum = 1;
- foreach my $p (@smooth) {
- foreach my $n (@h) {
- if (
- $p * $n <= $limit
- and (factor(euler_phi($n * $p)))[-1] <= 5
- ) {
- if ($p == 2) { # optional optimization
- foreach my $n (@h) {
- while ($n * $p <= $limit) {
- $sum += ($n * $p) % $mod;
- $sum %= $mod;
- $n *= $p;
- }
- }
- last;
- }
- else {
- $sum += ($n * $p) % $mod;
- $sum %= $mod;
- push @h, $n * $p;
- }
- }
- }
- say "$p -> $sum ($#h)";
- }
- say "Final answer: $sum";
|