Prime numbers

Prime

Prime numbers are important in Computer Science (For example: Cryptography) and finding prime numbers in a given interval is a "tedious" task. Usually, we are looking for big (very big) prime numbers therefore searching for a better prime numbers algorithms will never stop.

Standard prime testing

Pull out the sqrt call

The first optimization was to pull the sqrt call out of the limit test, just in case the compiler wasn't optimizing that correctly, this one is faster:

int is_prime(int n) {
  long lim = (int) sqrt(n);
  for (int i=2; i < =lim; i++) if (n%i == 0) return 0; return 1;}

Restatement of sqrt.

int is_prime(int n) {
  for (int i=2; i*i < =n; i++) if (n%i == 0) return 0;
  return 1;
}

Don't need to check even numbers

int is_prime(int n) {
  if (n == 1) return 0;         // 1 is NOT a prime
  if (n == 2) return 1;         // 2 is a prime
  if (n%2 == 0) return 0;       // NO prime is EVEN, except 2
  for (int i=3; i*i < =n; i+=2)   // start from 3, jump 2 numbers
    if (n%i == 0)               //  no need to check even numbers
      return 0;
  return 1;
}

A (very) little bit of thought should tell you that no prime can end in 0,2,4,5,6, or 8, leaving only 1,3,7, and 9. It's fast & easy. Memorize this technique. It'll be very helpful for your programming assignments dealing with relatively small prime numbers (16-bit integer 1-32767). This divisibility check (step 1 to 5) will not be suitable for bigger numbers. First prime and the only even prime: 2.Largest prime in 32-bit integer range: 2^31 - 1 = 2,147,483,647

Further, we can improve divisibility check for bigger numbers. Further investigation concludes that a number N is a prime if and only if no primes below sqrt(N) can divide N.

Solve UVA problems:

• 10539 - Almost Prime Numbers
• 10394 - Twin Primes
• 10852 - Less Prime
• 543 - Goldbach’s Conjecture

543 - Goldbach’s Conjecture

Every number greater than 2 can be written as the sum of three prime numbers.

Sample Input

8
20
42
0

Sample Output

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

Solution