isPrime, optimization 4

Check every number and keep the previosly generated primes. Use them to test the following numbers.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

const int PSIZE = 150000; int primes[PSIZE]; int sz = 0; bool isPrime4( int x ) { if(x < 2) return true; int limit = (int) sqrt(x); primes[sz] = limit+1; for(int *p = primes; *p <= limit; p++) { if( x % *p == 0 ) { return false; } } assert(sz < PSIZE); primes[sz++] = x; return true; }

Other entries:

• isPrime: Naive version 
• isPrime, Optimization 1: Iterate only until the square root of the number
• isPrime, Optimization 2: Only divide by odd numbers, until the square root of the number
• isPrime, Optimization 3: Skip the divisors that are multiple of 2 or 3
• Keep the previosly generated primes and use them to test the following numbers.
• isPrime, Recursive.

isPrime, optimization 3

Divisors start in 5. Skip the divisors that are multiple of 2 or 3.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

bool isPrime3( int x ) { if( x == 2 || x == 3) { return true; } if( x % 2 == 0 || x % 3 == 0 ) { return false; } int divisor = 5; int delta = 2; int limit = (int) sqrt(x); while( divisor <= limit ) { if( x % divisor == 0 ) { return false; } divisor += delta; delta = 6 - delta; } return true; }

Other entries:

• isPrime: Naive version 
• isPrime, Optimization 1: Iterate only until the square root of the number
• isPrime, Optimization 2: Only divide by odd numbers, until the square root of the number
• isPrime, Optimization 3: Skip the divisors that are multiple of 2 or 3
• Keep the previosly generated primes and use them to test the following numbers.
• isPrime, Recursive.

isPrime, optimization 1

It is not necessary to check divisors bigger than the square root of the number.

1 2 3 4 5 6 7 8 9

bool isPrime1( int x ) { int limit = (int) sqrt(x); for( int divisor = 2; divisor <= limit; divisor++ ) { if( x % divisor == 0 ) { return false; } } return true; }

• isPrime: Naive version 
• isPrime, Optimization 1: Iterate only until the square root of the number
• isPrime, Optimization 2: Only divide by odd numbers, until the square root of the number
• isPrime, Optimization 3: Skip the divisors that are multiple of 2 or 3

isPrime, optimization 2

Only divide by odd numbers, until the square root of the number.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

bool isPrime2( int x ) { if( x == 2 ) { return true; } if( x % 2 == 0 ) { return false; } int limit = (int) sqrt(x); for( int divisor = 3; divisor <= limit; divisor += 2 ) { if( x % divisor == 0 ) { return false; } } return true; }

Other entries:

• isPrime: Naive version 
• isPrime, Optimization 1: Iterate only until the square root of the number
• isPrime, Optimization 2: Only divide by odd numbers, until the square root of the number
• isPrime, Optimization 3: Skip the divisors that are multiple of 2 or 3
• Keep the previosly generated primes and use them to test the following numbers.
• isPrime, Recursive.