Thread: prime number program with function

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    29

    prime number program with function

    hi all, this is the next one i picked to do.

    -Finding Prime Numbers and Sum-

    An Integer is said to be prime if it is divisible by only 1 and itself. For example 2, 3, 5 and 7 are prime, but 4, 6, 8, and 9 are not.

    Write a program to determine which numbers between 1 and 1000 and prime.

    Use a function called primeNum to do the work.

    The prototype should look like the following:

    int primeNum (int); The function should see if the value passed in is prime. If the value is prime, the function should return 1. If the value is not prime, then the function should return 0. There should be no printfs in the function.

    Your main program should then print out the number if it is prime.
    Your main program should also print out the sum of all the prime numbers from 1 to 1000.

    Here’s the sample output:

    Prime Numbers are: 2,3,5,7,…….
    Sum of Prime Numbers from 1 to 1000: xxxx.

    Hint: Remember the % operator can tell you if a number is divisible by itself.

    i am totally lost in what im trying to do, and this is all ive come up with so far. Am I going about it the right way, passing the correct int to the function and the work with % to find the prime number. I have no idea how to use that to find a prime number so I just took a guess. Thanks for the help again I know im putting up more than my share up here but I'm trying to get better.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 1000;
    
    int main() {
        int primeNum (int);
        
        int i;
        
        for (i = 0; i <= MAX; i++) {  
        printf("Prime numbers are: %d",prime(i);}
    }
    
        
    system("PAUSE");
    return 0;
    }
    
    int primeNum (int i) {
    
        
            if (i % i == 0){
            return 1;
            }
            else {
                 return 0;
            }
            
        }

  2. #2
    Registered User
    Join Date
    Sep 2007
    Posts
    3
    I'm new to C so I hope this advice is useful.

    When using "#define MAX 1000;" you don't need a semi-colon also declaring functions is done outside the main function. You'll also need to re-arrange the loop so it also calculates the sum of prime numbers.

    Code:
    #include <stdio.h>
    
    #define MAX 1000
    
    int primeNum (int);
    
    int main()
    {
        int i;
        int sum = 0;
    
        for(i = 0; i <= MAX; i++){
    
    		if (primeNum(i) == 1){
    			printf("Prime number: &#37;d", i );
    			sum += i;
    		}
    	}
    	
    	printf("Sum of Prime Numbers: %d", sum );	
    
    	return 0;	
    }
    
    int primeNum(int i){
    
            if (i % i == 0)
    			return 1;
            else
                return 0;
    }
    The primeNum function is a lot more complicated than that. I'll explain that in the next post if you need more help.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    The hint is a little off. The &#37; operator tells you if one number is divisible by another, not necessarily by itself. That's important here.

  4. #4
    Registered User
    Join Date
    Sep 2007
    Posts
    29
    wow good eye on the define max lamanna, understand the return 1 and return 0 now and how its incorporated with loop. i went to test it though to see it work and it crashed, do you know why the reason might be?

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    3
    You should modify your loops so they start at 1 instead of 0. Using 0 with the mod operator(&#37 will probably crash your program.

    To calculate a prime number in the simplest way you need to check every number before by the actual number. For example, take 25. You need to get your function doing this....
    25 % 1
    25 % 2
    25 % 3
    25 % 4
    25 % 5
    etc.... right up to 25. While doing that, you need to check each time is (25 % x) == 0. Whenever it evaluates to true you should count how many times it happens. A prime number should have a count value of 2, meaning, the only time (25 % x) == 0 is when x = 1 and x = 25. In the case of 25, (25 % 5) == 0, so that means your counting variable would equal 3. Therefore, it isn't a prime number. In the primeNum function you'll need a loop to make quick work of all those calculations.


    In mathematics it's said that you don't need to check every value (eg./ 1 to 25) to see if for example 25 is a prime number. You need only check those values from 1 to the square root of 25. But I wouldn't worry about that at this time.

  6. #6
    Registered User
    Join Date
    Sep 2007
    Posts
    29
    so i tried to put this in the primeNum function, it doesnt run ofcourse so it's wrong but am I heading in the right direction?
    Code:
    int primeNum(int i){
           int a = 0;
            for (a = 0; a < i; a++){
            if (i &#37; a == 0)
    			return 1;
            else
                return 0;
                }
    }

  7. #7
    Registered User
    Join Date
    Sep 2007
    Posts
    3
    Yep you're getting there.
    Start the loop with "a = 1". Also make sure your other loop starts at 1. Also, I think "==" takes precedence over "%", so it's best to modify your if statement to:
    Code:
    if ( (i % a) == 0)
    Now when that condition is met, the function will return 1. But, that condition will be met with the very first number put through it... ie: the number 1. So every number will be reported as a prime. What you want to do is count how many times that condition is meant. If it's met once or twice then the number is a prime. So you make a separate if statement to check that value, if it's 2 or less then you return 1.

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by mackieinva View Post
    so i tried to put this in the primeNum function, it doesnt run ofcourse so it's wrong but am I heading in the right direction?
    Code:
    int primeNum(int i){
           int a = 0;
            for (a = 0; a < i; a++){
            if (i &#37; a == 0)
    			return 1;
            else
                return 0;
                }
    }
    You only need to check while a*a<i. If a*a reaches a number greater than i, then you know i is prime.
    Last edited by King Mir; 09-19-2007 at 09:11 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > Start the loop with "a = 1".

    It shouldn't start with 1, since you don't want to check for divisibility by 1 - that's automatic.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > You only need to check while a*a<i.

    It's necessary to check while a*a <= i (for example 9 == 3*3). But this is an optimization - the simplest way to get it working is just to check every number between 2 and a-1 (or a/2), though going only up to the square root is much faster for large i.

    Edit: Actually, I take it back - making the loop condition "a*a <= i" is just as simple, and much more efficient for large i, though it requires a little thought to see why it works. It's not quite as efficient as precomputing the integer square root of i, though that's just a small constant factor slowdown.
    Last edited by robatino; 09-19-2007 at 09:22 PM.

  11. #11
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Also, you want loop to check every number, and only return if it is divisible, until the loop finishes. After the loop finishes, you want to return 1.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  12. #12
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Another thing that will cut the time in half is that you don't need to check any even numbers after 2 since no prime number is even, so just start at 3 and increment by 2 in your for loop.

  13. #13
    Registered User
    Join Date
    Sep 2007
    Location
    South Africa
    Posts
    20
    so in essence what you are looking for is:

    Code:
    #define MAX 1000
    int primeNum(int num)
    /* will see if a number between 1 and 1000*/
    /* (inclusive) is prime or not */
    {
        int i, num_root;
        num_root = sqrt(num);
    
        if (0 == (num%2))
        {
            return 0;
        } 
        for (i=3; i<=(num_root); i+=2)
        {
            if (0 == (num%i))
            {
                  return 0;
            }
        }
        //printf("%d\n", num);
        return 1;
    }
    Have a look at this and see if you can understand whats going on.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Please don't just post the answer. That's just helping someone cheat!
    If they weren't going to spend the time to figure out how to write it themselves then they wont be figuring out how what you've posted works either.
    Good thing there's a bug in it anyway...
    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
    Registered User
    Join Date
    Sep 2007
    Location
    South Africa
    Posts
    20
    If they choose to cheat it's not my problem. Neither is the bug

    edit: Which seems to be that the function will not work for in input of 2. Note that there are at least 2 more bugs on top of this
    Last edited by wyliek; 09-20-2007 at 03:07 AM. Reason: bug

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  2. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  3. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  4. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 04:25 AM
  5. program error
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 11-15-2001, 10:20 AM