prime number routine

D

don

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....
 
J

Jonathan Turkanis

K

Ken

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}
 
K

kazack

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
 
J

John Harrison

Ken said:
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
 
C

Chris Theis

Jonathan Turkanis said:

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
 
C

Chris Theis

don said:
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
 
K

Karl Heinz Buchegger

don said:
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?
 
C

Chris Mantoulidis

don said:
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 :/
 
P

puppet_sock

don said:
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
 
B

Ben Dover

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.
 
J

Jonathan Turkanis

Chris Theis said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top