1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

finding prime numbers with c

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

  1. stefan1989

    stefan1989 New Member

    Joined:
    Apr 19, 2007
    Messages:
    4
    Likes Received:
    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. DaWei

    DaWei New Member

    Joined:
    Dec 6, 2006
    Messages:
    835
    Likes Received:
    5
    Trophy Points:
    0
    Occupation:
    Semi-retired EE
    Location:
    Texan now in Central NY
    Home Page:
    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."
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    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. stefan1989

    stefan1989 New Member

    Joined:
    Apr 19, 2007
    Messages:
    4
    Likes Received:
    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.
     
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    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.

    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
     
  6. stefan1989

    stefan1989 New Member

    Joined:
    Apr 19, 2007
    Messages:
    4
    Likes Received:
    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
  7. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    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
     

Share This Page