#include #include // 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 is not prime { return false; // treat negative numbers 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 and greater than 2 { int limit = int(sqrt(n) + 1); // largest divisor to check int divisor = 3; // initialize to smallest 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 if the function does not // return within the loop } }