UP / HOME

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

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: 2020-09-07 Mon 12:50 Emacs 26.3 (Org mode 9.1.9)