# Challenge 076

## Table of Contents

## 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: 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; }