# Thread: prime number program with function

1. ## 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 i;

for (i = 0; i <= MAX; i++) {
printf("Prime numbers are: %d",prime(i);}
}

system("PAUSE");
return 0;
}

if (i % i == 0){
return 1;
}
else {
return 0;
}

}```

2. 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 main()
{
int i;
int sum = 0;

for(i = 0; i <= MAX; i++){

printf("Prime number: &#37;d", i );
sum += i;
}
}

printf("Sum of Prime Numbers: %d", sum );

return 0;
}

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. 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. 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. 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. 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. 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. Originally Posted by mackieinva
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.

9. > 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. > 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.

11. 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.

12. 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. so in essence what you are looking for is:

Code:
```#define MAX 1000
/* 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. 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...

15. 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