Prime Numbers

This is a discussion on Prime Numbers within the C Programming forums, part of the General Programming Boards category; I'm busy with a code that should determine whether a certain value is a prime number or not. If the ...

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    33

    Prime Numbers

    I'm busy with a code that should determine whether a certain value is a prime number or not. If the number isn't prime, it should determine the smallest divisor of that value. Unfortunately, I'm having problems getting this to work..

    Code:
    #include <stdio.h>
    
    int main()
    {
        int input;/*input variable*/
        int i=1; /*used to loop the user input (user should enter an integer greater than '1'*/
        int div=0;/*used to determine the smallest divisor of the input value if it is not prime*/
        int n=3;/*used in formula to check odd numbers for prime.*/
        char rept;/*option to repeat program*/
        
        do
        {
            do
            { 
              input=i;
          
              printf("\nType a number >1: ");
              scanf("%d", &input);//integer input point
              getchar();//buffer filter
              i++;
              }
            while(i<=1);
        
              printf("\nYou entered %d.\n", input);
        
            if(input%2==0)
            {
              div+=i;//sum to determine the smallest divisor, if the input value is even (not prime)
              printf("\n%d is the smallest divisor of %d!\n", div, input);
              }
            else if(input%2==1)
            {
              n=input/n+1;//sum to determine which odd integers are not prime
              div+=n-1;//if the input is odd and is NOT prime, this sum determines the smallest divisor
    
              if(n%2==0)
              printf("\n%d is the smallest divisor of %d!\n", div, input);
             
              else if(n%2==1) 
              printf("%d is a prime number!\n", input);
              }
            printf("Would you like to try again (y/n)? ");
            scanf("%c", &rept);//option to repeat the program...
            getchar();//buffer filter
        }
        while(rept=='y'||rept=='Y');
        return 0;      
    }
    Last edited by SilentPirate007; 03-16-2010 at 11:14 AM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    So why don't you have two functions?
    - isPrimeNumber(n)
    - findLowestDivisor(n)

    It would
    a) make the code more readable
    b) allow you to test both functions separately

    Which would then enable you to say to us things like
    "findLowestDivisor() isn't working for odd numbers"
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Salem View Post
    So why don't you have two functions?
    - isPrimeNumber(n)
    - findLowestDivisor(n)
    Please don't, that's horribly inefficient. Because, probably, you need to find the lowest divisor to find out whether the number is a prime number. Probably, there should be one function, findLowestDivisor, which returns 0 (or whatever) when the number is prime.

    But I agree, the code is a (buggy) mess.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Couldn't you just do:

    if n == 1 return (true); // is prime
    else
    int n = 2;
    while(n <= sqrt(number))
    if(number % n == 0) return n; // return the divisor
    n++;

    return 0; // return 0 if the number is not prime

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    n == 1 doesn't need an else, since it would have the return statement.

    The while loop seems simple and clear. For larger number, I'd add a little logic to optimize it.

  6. #6
    Registered User
    Join Date
    Feb 2010
    Posts
    33
    I forgot to add, I can only use the standard input output library <stdio.h>. sqrt(number) requires <math.h> or at least won't work with stdio.h.

    Since some seem to find it hard to read, could anyone suggest a better format? It would help me alot...

    thanks

  7. #7
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    unsigned int low_d(unsigned int x)
    {
            unsigned int i;
    
            for (i = 2; i < x; i++){
                    if (!(x % i)){
                            return i;
                    }
            }
            return 1;
    }
    
    int main(void)
    {
            unsigned int i;
    
            for (i = 0; i <= 0xffffffff; i++){
                    if (low_d(i) == 1){
                            printf("%i\n", i);
                    }
            }
            return 0;
    }
    Like this, maybe?

    EDIT: Sorry, just got bored and was curious how long it would take to run. . . It's been about 3 hours and we're in the millions.

  8. #8
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by SilentPirate007 View Post
    I forgot to add, I can only use the standard input output library <stdio.h>. sqrt(number) requires <math.h> or at least won't work with stdio.h.

    Since some seem to find it hard to read, could anyone suggest a better format? It would help me alot...

    thanks
    Well you could iterate until number/2 instead of sqrt(number) if you are not allowed to use math.h . However, keep in mind this is less efficient. For example if number = 121 with sqrt(number) you would iterate until you reach 11 and conclude that 11 divides 121. with number/2 you are iterating 5 times more numbers.
    Last edited by claudiu; 03-16-2010 at 05:08 PM.

  9. #9
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,627
    Quote Originally Posted by EVOEx View Post
    Please don't, that's horribly inefficient. Because, probably, you need to find the lowest divisor to find out whether the number is a prime number. Probably, there should be one function, findLowestDivisor, which returns 0 (or whatever) when the number is prime.

    But I agree, the code is a (buggy) mess.
    How is splitting code into several functions inefficient?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Elysia View Post
    How is splitting code into several functions inefficient?
    The "usual" method for finding out whether an integer is a prime number is to test all divisors (from low to high) until it finds one. If you split the test whether it is a prime and finding the lowest divisor into two functions, you'd have to do something like this:
    Code:
    if(!isPrime(n))
      printf("%d\n", getLowestDivisor(n));
    But isPrime already calculates what getLowestDivisor must know and must probably recalculate. So I would prefer:
    Code:
    int divisor = getLowestDivisor(n);
    if(divisor)
      printf("%d\n", divisor);
    Of course, isPrime might cache the lowest divisor for the function getLowestDivisor. This can be done in two ways: it could store it in a map with lowest divisors. That's doable, even though it still adds a O(log m) complexity (where m is the size of the cache) that we shouldn't have. It could also just cache the lowest divisor of the last call to isPrime. That would work in this case, but once we extend the application to test two numbers at the same time, it won't.

  11. #11
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,627
    I see what you're getting at. But it's still essentially two tasks: one is finding the lowest divisor and one finding if it's a prime or not. So you could break it into two functions.
    You could use a common function, such as GetLowestDivisor, to combine these functions and return the lowest divisor. I see you didn't mean what I thought you meant, though. What you said came off as "making two functions out of one is inefficient"
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Elysia View Post
    I see what you're getting at. But it's still essentially two tasks: one is finding the lowest divisor and one finding if it's a prime or not. So you could break it into two functions.
    You could use a common function, such as GetLowestDivisor, to combine these functions and return the lowest divisor. I see you didn't mean what I thought you meant, though. What you said came off as "making two functions out of one is inefficient"

    Well, theoretically it IS less efficient... Pushing the parameters, calling... Pfew, that's gotta be at least 3 clock cycles ;-). (Actually, I bet it's a bit more, but still very little)

    I understand your design choice according to the idea that separate tasks should have different functions. However, you should also avoid repetitive code, and getLowestDivisor and isPrime would share most of their code. I'm not saying you wouldn't solve this properly, though, but how would you do it?

    I'd build two functions. getLowestDivisor, to get the lowest divisor (obviously) or 0 if there is no divisor. Then I would build:
    Code:
    bool isPrime(int n)
    {
      return getLowestDivisor(n) == 0;
    }
    No repetitive code, but two tasks split over two functions. However, the task specified here would probably only use getLowestDivisor.

    How would you do it - out of interest, even though I expect pretty much the same... I can't see any better way to do this.

  13. #13
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,627
    Well, meh, not sure what the lowest divisor actually is and I'd have to dig up my old find prime numbers code.
    But you know that the compiler will likely optimize that function call so no harm
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Quote Originally Posted by claudiu View Post
    Well you could iterate until number/2 instead of sqrt(number) if you are not allowed to use math.h . However, keep in mind this is less efficient. For example if number = 121 with sqrt(number) you would iterate until you reach 11 and conclude that 11 divides 121. with number/2 you are iterating 5 times more numbers.
    Or he could simply iterate up until sqrt(x) by doing it like this:
    Code:
    for (i = 2; i*i < x; i++)]
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Quote Originally Posted by EVOEx View Post
    Code:
    bool isPrime(int n)
    {
      return getLowestDivisor(n) == 0;
    }
    Isn't that two functions? Isn't that almost exactly what I put up there? Is there an echo in this thread?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Perfect and Prime numbers
    By taggrath in forum C++ Programming
    Replies: 3
    Last Post: 10-22-2009, 02:13 AM
  2. Finding Prime Numbers
    By dan724 in forum C Programming
    Replies: 11
    Last Post: 12-14-2008, 11:12 AM
  3. Checking very large prime numbers
    By password in forum C++ Programming
    Replies: 2
    Last Post: 02-11-2008, 11:26 AM
  4. Replies: 18
    Last Post: 11-04-2005, 01:41 PM
  5. Replies: 2
    Last Post: 09-11-2002, 05:00 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21