finding prime numbers with c

Discussion in 'C' started by stefan1989, Apr 19, 2007.

1. stefan1989New Member

Joined:
Apr 19, 2007
Messages:
4
0
Trophy Points:
0
hello, im trying to write a program that will find all the prime numbers in a given field. i've been reading forums ad looking at examples, but i cant comprehend it, so i figured it was time to make a post. i don't really know where to start. the only thing i can think of doing is having the program divide every number up to teh max i set by every number and only print the ones that are divisible by 1 and itself. this seems like a very primitive process and i'm wondering if there is an easier way to do it.

2. DaWeiNew Member

Joined:
Dec 6, 2006
Messages:
835
5
Trophy Points:
0
Occupation:
Semi-retired EE
Location:
Texan now in Central NY
The first thing you can do is throw away all the even numbers, since they're divisible by 2. Then, look at 3. Cross off every number greater than 3 that is a multiple of 3. Then go to the next number, 5, and cross off every number greater than 5 that is a multiple of 5. You get the picture. Google "Sieve of Eratosthenes."

Joined:
Jul 12, 2004
Messages:
15,293
365
Trophy Points:
83
You don't need to be dividing up to the max but just finding the remainder upto the n/2 or sqrt of n even will do but to start off you can loop till n/2.

4. stefan1989New Member

Joined:
Apr 19, 2007
Messages:
4
0
Trophy Points:
0
I already read the sieve of Eratosthenes and I understand it. My problem is applying it to a c program. I literally started c like 2 days ago lol and have been scouring forums trying to learn more. How do I eliminate all the eve numbers and number divisible by odd numbers with a few lines of code? The only way i can see doing it is writing a line for each number which is insane. Maybe I don't know enough C to tackle this problem.

Joined:
Jul 12, 2004
Messages:
15,293
365
Trophy Points:
83
And the problem is also for the type of guy who is 2 days in C. You will realize when you write it.

1. Read the content in to the array
2. Loop through then something like this pseudo code
Code:
```for(int i = 2;i<n/2;i++)
{
if(n % i == 0)
// n is not prime and set the flag
}
if(flag not set)
Number is prime```

6. stefan1989New Member

Joined:
Apr 19, 2007
Messages:
4
0
Trophy Points:
0
Ok, here is what i've got so far

Code:
```#include <stdio.h>
#include <conio.h>

main()
{
int i;
for(int i=2;i<n/2;i++)
{
if(n%i==0)
}
if(n%i???)   don't know what goes here.  if(i) ??
printf("%d",i);
}```

Last edited by a moderator: Apr 20, 2007

Joined:
Jul 12, 2004
Messages:
15,293
365
Trophy Points:
83
First you need to learn how to use the loops and ifs. Instead of solving the problem try something like user inputs a number as checks if its greater than 10 or less than 10. and then try to get the numbers till user enters 0 to see if its greater than 10 or not.

Code:
```for(int i=2;i<n/2;i++)
{
if(n%i==0)
}
```
This as far as I know looks like C but is not C