471,049 Members | 1,764 Online

# prime number routine

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....
Jul 22 '05 #1
11 6830 "don" <do*@panix.com> wrote in message
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....

http://www.cse.iitk.ac.in/news/primality.html
http://www.parashift.com/c++-faq-lite/

HTH.

Jonathan
Jul 22 '05 #2
Well, this is really inefficient, but

int i = inputted number
int j = i - 1;
int prime = 1; //0 for false, 1 for true
for (j > 1; j--)
{
if ( (i/ j == 0)
{
//is not prime
prime = 0;
break;
}
}
if (prime == 1) prime;

else { not prime}
"don" <do*@panix.com> wrote in message
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....

Jul 22 '05 #3
Well this isn't the best way to do it but here is an idea:

Take the number that was input and divide it by all numbers up to and
including that number.

Each time the number comes out even add 1 to count and when it is done if
count is greater than 2 then the number is not prime!!!

Or if you do not want to do it that way you can mod it up to and including
that number and each time that the mod is 0 then add 1 to count and if count
is > 2 then you know it is not prime!!!

Shawn
"don" <do*@panix.com> wrote in message
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....

Jul 22 '05 #4

"Ken" <s4******@student.uq.edu.au> wrote in message
news:c0**********@bunyip.cc.uq.edu.au...
Well, this is really inefficient, but

int i = inputted number
int j = i - 1;
int prime = 1; //0 for false, 1 for true
for (j > 1; j--)
{
if ( (i/ j == 0)
{
//is not prime
prime = 0;
break;
}
}
if (prime == 1) prime;

else { not prime}

Not only inefficient, its also incorrect, doesn't compile, doesn't work even
when syntax errors are fixed.

Please don't do others homework. Request for algorithm is OK, request for
code is not, at least in my book.

john
Jul 22 '05 #5

"Jonathan Turkanis" <te******@kangaroologic.com> wrote in message
news:c0*************@ID-216073.news.uni-berlin.de...
"don" <do*@panix.com> wrote in message
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....

http://www.cse.iitk.ac.in/news/primality.html

This is indeed a very fine piece of work! However, I doubt that it will be
of much help to a newbie because if you're able to understand the approach
to primality starting from Fermat's little theorem you can easily come up
with more trivial solutions.
BTW the Miller-Rabin-Probabilistic primality test is also nice :-)

Cheers
Chris
Jul 22 '05 #6

"don" <do*@panix.com> wrote in message
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....

There are various ways to test for primality. One would be the following:

Consider two thresholds (Min & Max) and an input variable x which you would
like to test for primality. A prime is typicall characterized by the fact
that the modulo division by another number should not equal 0, except that
number is the input value itself or 1. And this is exactly what the (quite
simple) algorithm builds on to.

First of all set Min and Max to 2. The basic idea is to test the modulo
division of our input x against a bunch of other numbers and we're trying to
keep this test efficient by eliminating redundant tests. Loop as long as Min 1 and x does not equal the Max threshold.

To begin with check whether the modulo division of x with Min (remember
that's 2 during the first looping) does not equal zero. If it does you can
immediately deduce that x is not a prime. If it does we adjust our Max
threshold by setting it to x / Min. This way we eliminated a whole lot of
redundant tests immediately. Furthermore check if Max <= 1. If this is true
then x is also a prime. Subsequently we will put our Max threshold into
action by testing whether x % Max != 0. If this is true then x is no prime
either, just as above. However, if it is not true we have to adjust our Min
threshold before starting the loop again. Our new Min threshold is set to x
/ Max + 1.

Well and that's all. This is certainly not the most efficient algorithm for
large prime numbers (there you have to resort to mathematical tests based on
Fermat's little theorem and probabilistic approaches), but it is certainly
more efficient than the brute force method.

HTH
Chris
Jul 22 '05 #7
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
Jul 22 '05 #8
"don" <do*@panix.com> wrote in message news:<c0**********@reader2.panix.com>...
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....

to see if k is prime, there are 2 ways:

1) test if any _integer_ from 2 to sqrt(k), and if that integer
divides k then k is not prime

2) do the following on startup to generate a prime list (i personally
hate this way even though it's good). Start from n=2 and continue for
as long as you (or the one who set the problem) want, and erase the
multiples of n from the prime list).

BTW: I think the first way is so easy you could've thought of it
yourself :/
Jul 22 '05 #9
"don" <do*@panix.com> wrote in message news:<c0**********@reader2.panix.com>...
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....

Precompute a big table of primes up to some maximum size.

Get your number. If it is smaller than the max, then
if it is in the table it is prime and if not not. Miller time.

If it is bigger than your max, then you have to start doing
some dividing. But first, you don't need to divide by anything
bigger than the square root of the number. (You have to explain
why.) And you don't need to divide by any number that is itself
not prime. (Again, you have to explain why.)

So, if your number is smaller than the square of the max of your
table, again, the scheme is pretty easy. You only need to divide
by the numbers in your table.

If your number is bigger than that, then you are on your own.
Socks
Jul 22 '05 #10
Let the number be n. If n is not prime, it is composite
and can be written as n=p*q. Let r = min(p,q). Then r is
at most sqrt(n). So you have to test for divisibility against
r/2 numbers to find a possible odd divisor.

Here is a simple brute force algorithm:

Input: non-negative integer n
Output: the answer to the question: "Is n a prime number?"
BEGIN
if n < 2 or n is even
then output NO
else if n==2
then output YES
else let i=3
while i < sqrt(n) do
if i divides n
then output NO
i = i+2
output YES
END

This algorithm is exponential in the length of the representation of the
number n.
As long as the number n is restricted to be less than, say, 10^10, it
shouldn't take too long.

On Tue, 10 Feb 2004 01:49:29 -0500, don <do*@panix.com> 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....

--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Jul 22 '05 #11
"Chris Theis" <Ch*************@nospam.cern.ch> wrote in message
news:c0**********@sunnews.cern.ch...

"Jonathan Turkanis" <te******@kangaroologic.com> wrote in message

http://www.cse.iitk.ac.in/news/primality.html

This is indeed a very fine piece of work! However, I doubt that it

will be of much help to a newbie because if you're able to understand the approach to primality starting from Fermat's little theorem you can easily come up with more trivial solutions.
The link was a bit tongue-in-cheek, since the OP explicitly said it
was for a homework assignment. However, you can find a lot of good
links on primality testing starting from the one I gave.
BTW the Miller-Rabin-Probabilistic primality test is also nice :-)

My old professor Bob Solovay had a good one, too.

Jonathan

Jul 22 '05 #12

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 36 posts views Thread by Dag | last post: by 9 posts views Thread by Greg Brunet | last post: by 11 posts views Thread by lostinpython | last post: by 2 posts views Thread by wudoug119 | last post: by 4 posts views Thread by SweetLeftFoot | last post: by 60 posts views Thread by rhle.freak | last post: by 7 posts views Thread by newstips6706 | last post: by 2 posts views Thread by QHorizon | last post: by 3 posts views Thread by MarkDoronin | last post: by reply views Thread by sjain6 | last post: by reply views Thread by Trc0g | last post: by reply views Thread by MartianBanks | last post: by reply views Thread by clicknium | last post: by reply views Thread by autodeveloper | last post: by reply views Thread by SwissProgrammer | last post: by 6 posts views Thread by Videot7 | last post: by 4 posts views Thread by mshakeelattari | last post: by