Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Jim Laird
    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
      void preload_pl(vector<int> &v)
      {
      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.