#include <iostream>
using namespace std;

// First 501 primes are found from 1 to 3571
const int SEARCH_TO = 1000000;
const int SEARCH_START = 3;

/*
 *  You can double check by comparing with the link below:
 *  http://en.wikipedia.org/wiki/List_of_prime_numbers
 *  to verify accuracy.
 */

int main() {
    cout << "1 is a prime number." << endl;
    cout << "2 is a prime number." << endl;
    int found = 2;
    int i;
    for ( i = SEARCH_START; i < SEARCH_TO; i+=2 ) {
        int qualifies = 1;
        for ( int j = i-2 ; j > 1; j-=2 ){
            if ( i % j == 0 ) {
                qualifies = 0;
                break;
            }
        }
        if ( qualifies ) {
           cout << i << " is a prime number." <<endl;
            found++;
        }
    }
    cout << "Found " << found << " primes in range "
         << 1 << " to " << SEARCH_TO << ".\n";
    return 0;
}