blob: 9b2e4cef891df1f5d58fa93619cd7c3b1261c97a (
plain)
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
|
#!/usr/bin/env perl
use strict;
use warnings;
use feature qw{ say signatures state };
no warnings qw{ experimental };
use List::Util qw{ sum sum0 max };
use Getopt::Long;
my $n = 9;
GetOptions( 'n=i' => \$n, );
use JSON;
my $json = JSON->new->space_after->canonical;
my @primes = reverse grep { is_prime($_) } 2 .. $n;
my @output = prime_sum( $n, \@primes );
map { say $json->encode($_) } @output;
say '';
say $json->encode( $output[0] );
sub prime_sum ( $n, $primes, $list = [], $depth = 1 ) {
my @output;
my %join;
my @list = ( [] );
OUTER: while (@list) {
my $e = shift @list;
for my $p ( $primes->@* ) {
my $new->@* = reverse sort $e->@*, $p;
my $sum = sum $new->@*;
my $join = join ' ', $new->@*;
next if $join{$join}++;
push @list, $new if $sum < $n;
push @output, $new if $sum == $n;
last OUTER if $sum == $n;
}
}
return @output;
}
sub is_prime ( $n ) {
my @factors = factor($n);
return scalar @factors == 1 ? 1 : 0;
}
sub factor ( $n ) {
my @factors;
for my $i ( 1 .. $n - 1 ) {
push @factors, $i if $n % $i == 0;
}
return @factors;
}
|
