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 (16bit integer 132767). 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 32bit 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

Input