blob: 6a480cbfe8bab847c36593f7462ea6f6bf5a4ade (
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
|
#+SETUPFILE: ~/.emacs.d/org-templates/level-2.org
#+HTML_LINK_UP: ../index.html
#+OPTIONS: toc:2
#+EXPORT_FILE_NAME: index
#+TITLE: Challenge 076
* 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.
** Perl
- Program: [[file:perl/ch-1.pl]]
- Help taken from: [[https://stackoverflow.com/a/35756072]].
User input is stored in =$input=.
#+BEGIN_SRC perl
my $input = shift @ARGV;
chomp $input;
#+END_SRC
1 is assumed not to be a prime number so we reject numbers less than or
equal to 1.
#+BEGIN_SRC perl
die "Invalid input, enter numbers greater than 1.\n" if $input <= 1;
#+END_SRC
If it's a prime number then the minimum sum is the number itself so we
just return it & exit.
#+BEGIN_SRC perl
say $input and exit 0 if is_prime($input) == 1;
#+END_SRC
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, [[https://en.wikipedia.org/wiki/Goldbach%2527s_conjecture][Goldbach's conjecture]] has been shown to hold for all integers
less than =4 × 10^18=.
#+BEGIN_SRC perl
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);
}
}
#+END_SRC
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=.
#+BEGIN_SRC perl
elsif (is_prime($input - 2)) {
say "2 + $input";
}
#+END_SRC
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.
#+BEGIN_SRC perl
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);
}
}
#+END_SRC
If $num is divisible by any number between 2 & =sqrt($num)= then it's not
prime.
#+BEGIN_SRC perl
sub is_prime {
my $num = shift @_;
foreach my $i (2 ... sqrt($num)) {
return 0 if $num % $i == 0;
}
return 1;
}
#+END_SRC
|
