Re: prime number routine
From: Karl Heinz Buchegger (kbuchegg_at_gascad.at)
Date: 02/10/04
- Next message: lallous: "Re: placement new , is this acceptable?"
- Previous message: Jonathan Turkanis: "Re: Making a program quicker tips..."
- In reply to: don: "prime number routine"
- Next in thread: Chris Mantoulidis: "Re: prime number routine"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 10 Feb 2004 12:29:59 +0100
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 kbuchegg@gascad.at
- Next message: lallous: "Re: placement new , is this acceptable?"
- Previous message: Jonathan Turkanis: "Re: Making a program quicker tips..."
- In reply to: don: "prime number routine"
- Next in thread: Chris Mantoulidis: "Re: prime number routine"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
