# prime number program with function

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 09-19-2007
mackieinva
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;
}

}

• 09-19-2007
lamanna
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.
• 09-19-2007
robatino
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.
• 09-19-2007
mackieinva
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?
• 09-19-2007
lamanna
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.
• 09-19-2007
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 a = 0;
for (a = 0; a < i; a++){
if (i &#37; a == 0)
return 1;
else
return 0;
}
}

• 09-19-2007
lamanna
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.
• 09-19-2007
King Mir
Quote:

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 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.
• 09-19-2007
robatino
> 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.
• 09-19-2007
robatino
> 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.
• 09-19-2007
King Mir
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.
• 09-20-2007
cpjust
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.
• 09-20-2007
wyliek
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.
• 09-20-2007
iMalc