Find the sum of all the prime numbers

Discussion in 'C' started by pradeep, Nov 29, 2006.

  1. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    A friend of mine who is learning to program in C, was having diffculty in writing a program to find the sum of all the prime numbers between a specified limit (in her case 3-60). I helped her out with the program, and I thought I'll post it here which might help others.

    Code:
     /*
     ** Program to find the sum of all numbers between 3 and 60
     ** @author : Pradeep
     ** @date : 11/29/2006
     */
     
     #include <stdio.h>
     
     void main(void)
     {
         unsigned int i,j,s=0,is_prime;
     
         for(i=3;i<=60;i++)
         {
             is_prime = 1; // Assuming that current value of i is prime
             
             // Checking for prime
             for(j=2;j<=(i/2);j++)
             {
                 if(i%j==0) // Not prime, set is_prime to 0 and break
                 {
                     is_prime = 0;
                     break;
                 }
             }
     
             if(is_prime) // If the number is prime, sum it up
             {
                 s += i;
                 // optionally you can print the prime numbers too
                 printf("%d ",i);
             }
         }
     
         printf("\n\nThe sum of the prime numbers = %d",s);
     }
     
  2. friendsforniraj

    friendsforniraj New Member

    Joined:
    Nov 24, 2006
    Messages:
    40
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    studying
    well this code is good but it ll take more time(for computational work)
    please check this code the 2nd for loop

    Code:
     /* ** Program to find the sum of all numbers between 3 and 60 ** @author : Pradeep ** @date : 11/29/2006 */  
    #include <stdio.h>  
    #include<math.h> 
    void main(void)
      { 
        printf("\n please enter the upper limit");
       int n;
        scanf("%d",&n);\\now n can be given by user
        unsigned int i,j,s=0,is_prime;     
        for(i=3;i<=n;i++) 
        {   
           is_prime = 1; // Assuming that current value of i is prime           
           // Checking for prime    
           for(j=2;j<=sqrt(i);j++)  
           {  
               if(i%j==0) // Not prime, set is_prime to 0 and break   
              {
                is_prime = 0;           
                break;       
               }  
           }     
         if(is_prime) // If the number is prime, sum it up     
          {  s += i;             // optionally you can print the prime numbers too 
                printf("%d ",i);  
           }  
       }   
       printf("\n\nThe sum of the prime numbers = %d",s);
     } 
    //see though your program will work proper but if we have to sum up prime nos. between 3 to n
    //where n verey big(though within the limits of int :) )
    // then the checkin condition from to n/2 will take lot of time
    // suppose ur n==100 then it will check from n=2 to n=50
    //so the no. of checking loops required for 100 will be 48
    //where as if we go from n=2 to n= 10 we only require 8 loops so it will be much faster
    // now think for the case of n=1000 wouldnt it will take lot of time
     
    Last edited by a moderator: Nov 29, 2006
  3. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    I understood your point, but I see you have used sqrt() ! How does that help?? And we need to check whether it got a factor execpt for itself and 1 or not.
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    I would use
    t = sqrt(i);
    in
    for(j=2;j<=sqrt(i);j++)
    e.g.
    for(j=2;j<=t;j++)
    So it does not need to calc square root all the time it loops through j
     
  5. friendsforniraj

    friendsforniraj New Member

    Joined:
    Nov 24, 2006
    Messages:
    40
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    studying
    yes i got you!
    the thing is we dont need to go more than the sqrt of the no. which to be checked as prime if it is not divisibe by any no. upto sqrt(n) than there wont be any factor above that you can check it for any no.
     
  6. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    Its not using square root anywhere, and neither does it require too. Could you please tell me why does it need to use square root??
     
  7. friendsforniraj

    friendsforniraj New Member

    Joined:
    Nov 24, 2006
    Messages:
    40
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    studying
    good point shabbir
     
  8. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    He edited the code to find a no is prime or not to loop till the sqrt(n) and not till n/2
     
  9. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    For example, sqrt(60) = 7.46, that means we will loop 7 times, but 60 is divisible by 30 also.
    The program works fine with sqrt, but what is the logic?
     
  10. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  11. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    There is other method also which does not require sqrt.

     
  12. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,645
    Likes Received:
    87
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    http://blog.pradeep.net.in
    Interesting, so we will find the factor of n within any of the number in sqrt(n) if not then its a prime number.
     
  13. friendsforniraj

    friendsforniraj New Member

    Joined:
    Nov 24, 2006
    Messages:
    40
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    studying
    let me tell you the logic now
    it is very simple
    look if k is any no.
    then k can be represented as k=i*j
    where i and are k's factor
    now i varies from 1to k
    and j varies from k to 1
    but for prime no. we check for i=2 to k/2
    acordingly j will varies from (k/2) to 2
    now if 2 is a factor of k
    then automatically k/2 is also a factor and so on
    that is when i increases, j decreases
    so we continue like this then there is condition that both i and j becomes equal
    so i*i=k
    so i=sqrt(k)
    but if k is not a square of any no. then i increases upto a integer just less than sqrt iof k
    thats all what i did
    now try this problem
    for a given no. print all its prime factors that is
    if input is 12 out put should be 2*2*3
    using the hint that the lowest factor of any no. other than one is always prime
    try it
     
  14. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    friendsforniraj thats a good logic explained.
     
  15. friendsforniraj

    friendsforniraj New Member

    Joined:
    Nov 24, 2006
    Messages:
    40
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    studying
    thank u sir
    but ma name is niraj
     
  16. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    I will try putting that from now on.
     
  17. rahul.mca2001

    rahul.mca2001 New Member

    Joined:
    Feb 13, 2008
    Messages:
    103
    Likes Received:
    0
    Trophy Points:
    0
    why do we need a square root
     
  18. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Excellent explaination. Now any one can understand either he is new or experience
     
  19. oleber

    oleber New Member

    Joined:
    Apr 23, 2007
    Messages:
    37
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Software Developer (Perl, C/C++ and Java)
    Location:
    Hamburg, Germany
    Home Page:
    http://oleber.freehostia.com/
    for(j=2;j<=sqrt(i);j++) :cryin:

    is similar to

    for(j=2;j*j <= i;j++) :p

    so, no sqrt in here since it is really slow. At least if was some years ago.
     
  20. oleber

    oleber New Member

    Joined:
    Apr 23, 2007
    Messages:
    37
    Likes Received:
    2
    Trophy Points:
    0
    Occupation:
    Software Developer (Perl, C/C++ and Java)
    Location:
    Hamburg, Germany
    Home Page:
    http://oleber.freehostia.com/

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice