https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method/
// A optimized school method based C++ program to check // if a number is prime
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
When you search for primes you can loop through all the numbers between 2 and your number to see if they divide into your number.
for (int i=2; i < n; i=i+1)
if (n%i == 0)
return false;
But that checks a lot of number you don't need to.
The first observation (optimization) is that any multiple of 2 (even number) is already checked by simply doing a divide by 2 check once.
So now we do a check for 2 and then skip every other even character.
if (n%2 == 0 ) return false;
for (int i=3; i < n; i=i+2)
if (n%i == 0)
return false;
The next observation (optimization) is that you can do nearly the same thing for three. So the first test covers all combinations of 2 and three. Now in the loop you skip every 6 numbers (2*3) and do some tests to cover all numbers that are not multiples of 2 or 3 that happen in between.
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i<n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
So this is simply an optimization that means you do not have to try every number.
The next observation we make is that you don't need to try numbers greater than the square root of n (these will never divide into n). So you can limit your loop to i*i < n
as i*i
is faster than sqrt(n)
.
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
Though personally I would do sqrt()
once rather than i*i
every time around the loop. But that may be slower for small values of n
.