Well so long as your values don't grow too large, then create a table with a search facility
Code:
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <iomanip>
using namespace std;
// See prime number theorem at
// http://www.utm.edu/research/primes/howmany.shtml
// this tells you how big your table may grow
// depending on how many you want to store
const int MAX_NUM = 100;
const int MAX_PRIMES = 50;
int primes[MAX_PRIMES];
int num_primes = 0;
void generate_table ( void ) {
int i,j;
num_primes = 0;
primes[num_primes++] = 2;
for ( i = 3 ; i < MAX_NUM ; i++ ) {
int lim = (int)sqrt((double)i);
bool composite = false;
for ( j = 2 ; j <= lim && !composite ; j++ ) {
composite = i % j == 0;
}
if ( !composite ) {
primes[num_primes++] = i;
}
if ( num_primes == MAX_PRIMES ) {
cout << "Table Full" << endl;
return;
}
}
}
void print_table ( void ) {
int i;
for ( i = 0 ; i < num_primes ; i++ ) {
cout << primes[i] << endl;
}
cout << "Expected number of primes is "
<< (int)(MAX_NUM/log((double)MAX_NUM))
<< endl;
cout << "Actual number of primes is "
<< num_primes
<< endl;
}
// a pair of functions to conduct a binary search of
// the table of primes created previously
int compare ( const void *key, const void *data ) {
const int *key_ptr = (const int*)key;
const int *data_ptr = (const int*)data;
if ( *key_ptr < *data_ptr ) return -1;
if ( *key_ptr > *data_ptr ) return +1;
return 0;
}
bool search_table ( int test_val ) {
return bsearch( &test_val, primes, num_primes, sizeof(primes[0]), compare ) != NULL;
}
int main ( ) {
generate_table();
print_table();
for ( int i = 1 ; i < MAX_NUM ; i++ ) {
if ( search_table(i) ) {
cout << i << " is prime" << endl;
}
}
return 0;
}
Experiment a little - store the first 10000 primes in this table, and run your search loop thereafter
Something like
Code:
if ( x <= primes[num_primes-1] ) {
// its in the table, use search_table(x)
} else {
// x is too big to be in the table, start the search loop
}
??? Any Suggestions for Speeding This Up ???
