Thread: C Program for Prime Numbers

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    6

    Question 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!

  2. #2
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,823
    What do you have so far?

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    6
    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.

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    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]

  5. #5
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>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 :-)
    *Cela*

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    6
    Ok, that all gives me a better idea, thanks.

  7. #7
    Registered User Azuth's Avatar
    Join Date
    Feb 2002
    Posts
    236
    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?
    Demonographic rhinology is not the only possible outcome, but why take the chance

  8. #8
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>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.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  9. #9
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>But then you're not calculating them, your looking them up, which is a different thing altogether.
    Right, it's faster :-)
    *Cela*

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    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.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Feb 2003
    Posts
    17
    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);
    	}
    }

  12. #12
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    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.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

    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.
    Last edited by quzah; 02-19-2003 at 04:57 AM.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Client-server system with input from separate program
    By robot-ic in forum Networking/Device Communication
    Replies: 3
    Last Post: 01-16-2009, 03:30 PM
  2. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  3. somebody help me with this array program
    By hieugene in forum C++ Programming
    Replies: 2
    Last Post: 11-07-2006, 05:53 AM
  4. Need a little help with Cyclic Numbers Program
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 10-19-2005, 05:01 PM
  5. Perfect Numbers C Program
    By SlayerBlade in forum C Programming
    Replies: 2
    Last Post: 08-28-2005, 05:11 PM