AP Computer Science Workshop

---

Example: Finding Primes

---

#include <iostream.h>
#include <bool.h>
#include <math.h>

bool IsPrime(int num);      // function prototype

int main( )
{ int first, last;

    cout << "find primes between what two numbers: ";
    cin >> first >> last;

    int k;                 // variables can be declared anywhere in block
    for (k = first; k <= last; k++) 
    {
        if (IsPrime (k))
            cout << k << endl;
    }
    return 0;
}

bool IsPrime (int num)
// precondition: num >=2
// postcondition: returns 1 if num is prime, else 0
{
    if (num == 2)         // the only even prime
        return true;
    else if (num % 2 == 0)     // other even numbers are composite
        return false;
    else
    {
        bool prime = true;
        int divisor = 3;
        int upperLimit = static_cast<int>(sqrt(num) + 1);
        while (divisor <= upperLimit)
        {
            if (num % divisor == 0)
                prime = false;
            divisor +=2;
        }
        return prime;
    }
}

---

Mark Stehlik, Carnegie Mellon University