blob: 1653e8e9153edea138ce5565163464c1b69ff022 (
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
━━━━━━━━━━━━━━━
CHALLENGE 076
━━━━━━━━━━━━━━━
Table of Contents
─────────────────
1 Task 1 - Prime Sum
.. 1.1 Perl
1 Task 1 - Prime Sum
════════════════════
You are given a number `$N'. Write a script to find the minimum number
of prime numbers required, whose summation gives you `$N'.
• For the sake of this task, please assume 1 is not a prime number.
1.1 Perl
────────
• Program: [file:perl/ch-1.pl]
• Help taken from: [https://stackoverflow.com/a/35756072].
User input is stored in `$input'.
┌────
│ my $input = shift @ARGV;
│ chomp $input;
└────
1 is assumed not to be a prime number so we reject numbers less than
or equal to 1.
┌────
│ die "Invalid input, enter numbers greater than 1.\n" if $input <= 1;
└────
If it's a prime number then the minimum sum is the number itself so we
just return it & exit.
┌────
│ say $input and exit 0 if is_prime($input) == 1;
└────
If `$input' is even then we loop from 2 to `$input / 2' & check if
both `$i' & `$diff' are primes. If both are primes then we have our
numbers.
Eventually we'll find 2 primes to be a sum of even numbers. From
WikiPedia, [Goldbach's conjecture] has been shown to hold for all
integers less than `4 × 10^18'.
┌────
│ if ($input % 2 == 0) {
│ foreach my $i (2 ... $input / 2) {
│ my $diff = $input - $i;
│ say "$i + $diff"
│ if is_prime($i) and is_prime($diff);
│ }
│ }
└────
If the input is odd then we first check if `$input - 2' is a prime, if
it is then input is the sum of two primes, 2 & `$input - 2'.
┌────
│ elsif (is_prime($input - 2)) {
│ say "2 + $input";
│ }
└────
If even that doesn't match then the minimum sum will have three
numbers. 3 & then we use the same function as for even numbers to find
the other two primes.
┌────
│ else {
│ foreach my $i (2 ... ($input - 3) / 2) {
│ my $diff = $input - 3 - $i;
│ say "3 + $i + $diff"
│ if is_prime($i) and is_prime($diff);
│ }
│ }
└────
If $num is divisible by any number between 2 & `sqrt($num)' then it's
not prime.
┌────
│ sub is_prime {
│ my $num = shift @_;
│
│ foreach my $i (2 ... sqrt($num)) {
│ return 0 if $num % $i == 0;
│ }
│ return 1;
│ }
└────
[Goldbach's conjecture]
https://en.wikipedia.org/wiki/Goldbach%2527s_conjecture
|
