primes.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
#include <cmath>             // for sqrt
using namespace std;

// program to check for primeness
// Owen Astrachan, 4/1/99

bool IsPrime(int n);          // determines if n is prime

int main()
{
    int k,low,high;
    int numPrimes = 0;
    cout << "low number> ";
    cin >> low;

    cout << "high number> ";
    cin >> high;
    
    cout << "primes between " << low << " and " << high <<  endl;
    cout << "-----------------------------------" << endl;

    k = low;
    while (k <= high)
    {   if (IsPrime(k))
        {   cout << k << endl;
            numPrimes += 1;
        }
        k += 1;
    }
    cout << "-----------------" << endl;
    cout << numPrimes << " primes found between " << low
         << " and " << high << endl;

    return 0;
}

bool IsPrime(int n)
// precondition: n >= 0
// postcondition: returns true if n is prime, else returns false
//                returns false if precondition is violated     
{
    if (n < 2)                           // 1 and 0 aren't prime
    {   return false;                    // treat negative #'s as not prime
    }
    else if (2 == n)                     // 2 is only even prime number
    {   return true;
    }
    else if (n % 2 == 0)                 // even, can't be prime
    {   return false;
    }
    else                                  // number is odd
    {   int limit = int(sqrt(n) + 1);     // largest divisor to check
        int divisor = 3;                  // initialize to smallest divisor

        // invariant: n has no divisors in range [2..divisor)
	
        while (divisor <= limit)
        {   if (n % divisor == 0)         // n is divisible, not prime
            {   return false;
            }
            divisor += 2;                 // check next odd number      
        }
        return true;                      // number must be prime
    }
}