My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
Primes  
Updated Jun 17, 2010 by snakev...@gmail.com

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).

Powered by Google Project Hosting