# C Program for Prime Numbers

• 02-18-2003
mmuhlenb
C 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-2003
Govtcheez
What do you have so far?
• 02-18-2003
mmuhlenb
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-2003
Shiro
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.

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-2003
Cela
>>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-2003
mmuhlenb
Ok, that all gives me a better idea, thanks.
• 02-18-2003
Azuth
Quote:

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 :-)
Cela, were you born nasty, or did you develop those skills over time? ;)
• 02-18-2003
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
• 02-18-2003
Cela
>>But then you're not calculating them, your looking them up, which is a different thing altogether.
Right, it's faster :-)
• 02-18-2003
quzah
Quote:

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

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-18-2003
xenodvs1
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-2003
Hammer
Quote:

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.

Not really, if the number entered is prime but not in the lookup table, the program won't be able to tell its prime. Yeah, OK, it could return an "out of range" response, but would that be acceptable as it doesn't meet the requirements (imho)? Anyway, pointless argument, both ways are fine, its up the OP to determine the program requirements.
• 02-19-2003
quzah
Quote:

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.
It was more a lesson for the original poster. Be specific in what you need. Both examples above would fit their description of it.

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.
This was more a lesson to the original poster. Be specific, or you'll likely not get what you hope to. Both examples in this thread answer their problem 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.