Sorry, an error occurred while loading the content.

## RE: [PrimeNumbers] Re: Program for testing small numbers

Expand Messages
• Here s a simple, simple prime number tester for very small numbers. It saves the previous results of test searches in memory, so it will be impractical if you
Message 1 of 8 , Sep 7, 2004
Here's a simple, simple prime number tester for very small numbers. It
saves the previous results of test searches in memory, so it will be
impractical if you search for primes that are too large (depending on
how much memory is on your system). It also uses STL classes for
containers etc. Worked on my system. Change main() as required. Only
checks up to the square root of the test number as a slight
optimization.

Cheers, Jim

========================================================================
=====

#include <string>
#include <vector>
#include <ostream>

using namespace std;

// loads the prime list with the initial primes
{
v.resize(6);
v[0]=2; v[1]=3; v[2]=5;
v[3]=7; v[4]=11; v[5]=13;
return;
}

// returns true if testnum is prime. Adds primes to v as necessary
bool test_prime(int testnum, vector<int> &v)
{
// check the first few primes
for (unsigned int i = 0; i < 5; i++)
if (testnum % v[i] == 0) return false;

// check the rest of the list
for (unsigned int i = 5; i < v.size(); i++) {
if (testnum % v[i] == 0) return false;
if (testnum < (v[i]*v[i])) return true;
}

// at the end of the prime list, increase it till you hit the
test
// or determine that testnum is composite

for(int x = v[v.size()-1] + 2; ; x += 2) {
if (test_prime(x, v) == true) {
v.push_back(x);
if (testnum % x == 0) return false;
if ((x*x) > testnum) return true;
}
}
}

void main(int argv, char **argc)
{
vector<int> base_primes;

// initialize vector
base_primes.reserve(1000); // make room for 1000
entries to begin with
preload_pl(base_primes); // initialize the prime
list

// sieve numbers between 1001 and 10000
cout << "Primes between 1001 and 10000\n";
for (int test = 1001; test < 10000; test += 2) {
if (test_prime(test, base_primes) == true) {
cout << test << ", ";
}
}

return;
}
Your message has been successfully submitted and would be delivered to recipients shortly.