// con1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <math.h>

using namespace std;

int main()
{
	int n, numDiv = 0, i;
	cout << "Enter an int ";
	cin >> n;

	// note that this time we are not going all the way up to n.
	// only up to sqrt(n), so we don't expect prime numbers to be
	// divisible by 2 numbers in the range 1..n. Instead, we expect
	// prime numbers to be divisible only by one number in the range
	// 1..sqrt(n)+1.  See the sidenote at the end of the code...
	for (i = 1; i <= sqrt(n) + 1; i++) {
		if (n%i == 0) {
			numDiv++;
			if (numDiv >= 2) // I already know the number is not prime,
				break;		 // no point in checking the rest of i values
		}
		//...       // break will skip lines of code here to the end
					// of the loop and exit the loop
	}

	if (numDiv == 1)
		cout << "prime" << endl;
	else cout << "Not prime" << endl;

	// sidenote:
	// =========
	// If you want, you can change the loop to go from 2..sqrt(n)+1
	// and in that case you expect prime numbers not to be divisible
	// by ANY numbers in that range.

	return 0;
}


/*
i=1..n    see if (n%i == 0) numDiv++?  after loop, prime if numDiv==2
i=1..n    same above, end loop if numDiv>2
   same as above, i = 1..sqrt(n)+1
only check odd numebrs

982451653
*/