# 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

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;
}
```

Andinus / / Modified: 2021-09-13 Mon 15:37 Emacs 27.2 (Org mode 9.4.4)