I need to write a program that determines if a number entered is prime or not. Any help would be great! Thanks!

Printable View

- 02-18-2003mmuhlenbC Program for Prime Numbers
I need to write a program that determines if a number entered is prime or not. Any help would be great! Thanks!

- 02-18-2003Govtcheez
What do you have so far?

- 02-18-2003mmuhlenb
Well, I don't really have anything. I've been thinking about how to do it, using % and stuff like that and nothing is coming is working, b/c everything I think of I can think of a way that would fail.

- 02-18-2003Shiro
A number larger than one which has only two divisors is a prime number. Since each number larger than one is divisible by one and it is divisible by itself, this means that no other numbers between one and the number itself are allowed to be divisors.

So a very simple algorithm would consist of a loop, running from one to the number and check if the numbers inbetween are divisors. If such a number is found, then the number to be checked is not prime. There are more sophisticated algorithms which can determine faster if a number is prime or not, but this one is most easy to understand, I think.

[edit]

The %-operator is the remainder.

5 % 2 = 1

If A is a divisor of B, then the following condition should evaluate to true:

B % A = 0

[/edit] - 02-18-2003Cela
>>I need to write a program that determines if a number entered is prime or not.

Get a list of known prime numbers, make a static array out of those numbers, then binary search that array when you need to test for primality. It's way better than calculating your primes :-) - 02-18-2003mmuhlenb
Ok, that all gives me a better idea, thanks.

- 02-18-2003AzuthQuote:

*Originally posted by Cela*

**Get a list of known prime numbers, make a static array out of those numbers, then binary search that array when you need to test for primality. It's way better than calculating your primes :-)**

- 02-18-2003Hammer
>>It's way better than calculating your primes

But then you're not calculating them, your looking them up, which is a different thing altogether. :D - 02-18-2003Cela
>>But then you're not calculating them, your looking them up, which is a different thing altogether.

Right, it's faster :-) - 02-18-2003quzahQuote:

*Originally posted by Hammer*

**>>It's way better than calculating your primes**

But then you're not calculating them, your looking them up, which is a different thing altogether. :D

**calculate**primes. He asked how to determine if a number is a prime. Big difference.

It pays to be specific.

Quzah. - 02-18-2003xenodvs1
hope this helps

Code:`{`

Prime == 1;

gpf = floor(sqrt(y));

for(fact=2; fact <= gpf; fact++)

{

while( y % fact == 0)

{

if(Prime==1)

{

printf("%d = %d", y, fact);

Prime == 0;

}

else

{

printf(" * %d", fact);

y = y/fact;

}

if(Prime == 0)

{

printf("%d is a prime number.", y);

}

}

- 02-19-2003HammerQuote:

*Originally posted by quzah*

**Read the original question. He did not ask how to****calculate**primes. He asked how to determine if a number is a prime. Big difference.

It pays to be specific.

Quzah.

- 02-19-2003quzahQuote:

*Originally posted by Hammer*

**Not really, if the number entered is prime but not in the lookup table, the program won't be able to tell its prime.**

Besides, unless you plan on doing a huge number library to support the entering of numbers greater than four billion, you can easily create a table for it.

As such, the limitation would actually be on your compiler, before it would be a limitation of your program.

For example, using the above code to calculate if a number is prime, I could have it output the source code for a file that would do lookup by table; having the output of the test loop write the number into a cell in an array's initialization.

Quote:

Anyway, pointless argument, both ways are fine, its up the OP to determine the program requirements.

**as described to us**. Therefore, they are the one who ended up making specifications, or not making, as far as we, the forum readers, are concerned.

Quzah.