don wrote:

Ok, this is a homework assignment, but can you help me out anyway...... I

need a routine for figuring out if a number inputted by the user is a prime

number or not...... all I'm asking for is Not the exact code ( well maybe a

little) but the logic or algorithm to tell whether or not a number is

prime....

For all the regulars: The follwing is a simple exmplanation

which does not take any optimization or efficiency into account.

It is ment to bring the OP up to speed.

Well. When is a number considered to be prime?

A number is prime, if there is no other number except

1 and the number itself which divides that number evenly.

Example:

5 is prime, since you cannot find another number except

1 and 5, which divides 5

15 is not prime, since 5 divdes 15 evenly

it is very clear, that if such a potential divisor exists, it cannot be

greater then the number itself because in that case the quotient will

always be less then 1. Example: 15 / 32. Even if we don't know the

exact result, we know for sure that 15 / 32 will be less then 1.

OK. So from this we know, that it is sufficient to test all numbers

starting from 2 up to out number in question minus 1. If such a test

number divides the number in question, then the number in question

is not a prime number, otherwise it is.

Example:

5

quotient remainder

5 / 2 2 1

5 / 3 1 2

5 / 4 1 3

In no case were we left with a remainder of 0, which would indicate

an even division. Thus 5 is prime.

15

quotient remainder

15 / 2 7 1

15 / 3 5 0

Uups: 25 is evenly divisable by 5, thus 25 is not a prime

number.

So what did we do?

We looped (hint!) through some test numbers to see if one

of them devides our number evenly (remainder == 0)

If one does, then the number is not prime.

Now this translates nicely into a programming structure

int Number = 25;

bool IsPrime = true; // assume number is prime

// if one of the tests shows that the assumption

// is wrong, this flag will be changed

for( int TestNumber = 2; TestNumber < Number; TestNumber++ )

{

if( Number % TestNumber == 0 )

IsPrim = false;

}

if( IsPrime )

std::cout << Number << " is prime\n";

else

std::cout << Number << " is not prime\n";

Now that we have a working solution it is time to think about ways to

improve it. For this you have 2 answer 2 questions:

* is it really neccessary to test all numbers up to Number - 1?

* once a divisor is found, is it really neccessary to test other numbers?

--

Karl Heinz Buchegger

kb******@gascad.at