Consider:

All composite numbers have a factor equal or less than it's square root

1: therefore, if you are testing for the primeness of 'n', you need to see if all the numbers between 1 and sqrt(n) are a factor of n.

2: if you determin that 'a' is not a factor of n, then you do not need to check any multiple of 'a'

3: 'a' is a factor of 'n' if: n%a==0 or correctly mathmaticaly notated: a n(mod a) = 0 -> 'a' is a factor of 'n'

we will take advantage of statement (2) only in that if n is not even, it has no even factors

so, this is what you might do:

long int max,n,f;

void main ()

{

cin >> n; //get a number

max=sqrt(n)+1; //determine how far we need to go to prove primness.

//add 1 to compensate for integer math truncation

if (n % 2 == 0) //if it is divisable by 2

{

cout << "\nnot prime\n"; //then it is defenatly not prime

return;

}

else

{

for (f=3; f < max; f+=2) //start at 3, go up by 2 (hitting the odd numbers)

if (n%f == 0) //if 'f' is a factor of 'n'

{

cout << "\nnot prime\n"; //it's not prime

return;

}

}

//we've tried all the possibilities, so it must be prime

cout << "\nPrime!\n";

return;

}

Well, that has some buggs (it will tell you that 2 is not prime, for example) but its a big start. If you want to see the source for the one I wrote a while (it's quite nice) just say so. Also, to prove the primeness of really large numbers, you might consider useing 'long unsigned int' or if your compiler supports it 'long long unsigned int'