1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

finding prime numbers with c

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

  1. stefan1989

    stefan1989 New 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.
     
  2. DaWei

    DaWei New Member

    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

    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

    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

    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

    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

    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