I need to write a program that determines if a number entered is prime or not. Any help would be great! Thanks!
Printable View
I need to write a program that determines if a number entered is prime or not. Any help would be great! Thanks!
What do you have so far?
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.
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]
>>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 :-)
Ok, that all gives me a better idea, thanks.
Cela, were you born nasty, or did you develop those skills over time? ;)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 :-)
>>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
>>But then you're not calculating them, your looking them up, which is a different thing altogether.
Right, it's faster :-)
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.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
It pays to be specific.
Quzah.
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);
}
}
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.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.
It was more a lesson for the original poster. Be specific in what you need. Both examples above would fit their description of it.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.
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.
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.Quote:
Anyway, pointless argument, both ways are fine, its up the OP to determine the program requirements.
Quzah.