finding prime numbers with c

stefan1989's Avatar, Join Date: Apr 2007
Newbie Member
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.
0
DaWei's Avatar, Join Date: Dec 2006
Team Leader
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."
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
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.
0
stefan1989's Avatar, Join Date: Apr 2007
Newbie Member
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.
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by stefan1989
I literally started c like 2 days ago lol and have been scouring forums trying to learn more.
And the problem is also for the type of guy who is 2 days in C. You will realize when you write it.

I will help you with some flow chart type of thing

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
0
stefan1989's Avatar, Join Date: Apr 2007
Newbie Member
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 shabbir; 20Apr2007 at 18:20.. Reason: Code block
0
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
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