This wiki describes the algorithm used for the Summation of Four Primes problem from UVa Online Judge.
The problem
With one line of input containing one integer N which is within the range of N <= 10,000,000, its one line of output is expressed with a summation of four prime integers. If N's output cannot be expressed with four primes, then the line "Impossible." will be printed.
The algorithm
If N < 8:
- The output is "Impossible.".
If N is even:
- Subtract 4 (therefore, the first two prime numbers in the summation are 2 and 2).
- If new value of N is 4, then the summation consists of 2, 2, 2, 2.
- Subtract next non-even prime k.
- Check if new value is prime, if true: return the list of four prime numbers, else: add k back, repeat previous step until the new value is prime.
If
N is
odd:
- Subtract 5 (therefore, the first two prime numbers in the summation are 2 and 3).
- If new value of N is 4, then the summation consists of 2, 3, 2, 2.
- Subtract next non-even prime k.
- Check if new value is prime, if true: return the list of four prime numbers, else: add k back, repeat previous step until the new value is prime.
To test if a value, j, is prime: If j <= 3137 (the last prime up to the square root of 10 million):
- check if j > 1471 (a prime roughly half way between 2 and 3137).
- if true: iterate through a list of primes up to 3137 starting at 1471 (inclusive), else: iterate from 2 to 1471 (exclusive) (this separation speeds up the algorithm).
- if j is contained within the list of primes, return true, else: return false.
If
j > 3137:
- iterate through the list of primes and check if j is divisible by any prime.
- if true: return false, else: return true (a prime can only be divisible by 1 and itself).