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
-
Input