Find the sum of all the prime numbers

pradeep's Avatar author of Find the sum of all the prime numbers
Contributed by ()
This is an article on Find the sum of all the prime numbers in C.
Rated 5.00 By 1 users
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: C
/*
 ** 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);
 }
Go4Expert Member
29Nov2006,15:06   #2
friendsforniraj's Avatar
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 shabbir; 29Nov2006 at 15:35.. Reason: Code formating.
Team Leader
29Nov2006,15:33   #3
pradeep's Avatar
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.
Go4Expert Founder
29Nov2006,15:36   #4
shabbir's Avatar
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
Go4Expert Member
29Nov2006,15:41   #5
friendsforniraj's Avatar
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.
Team Leader
29Nov2006,15:41   #6
pradeep's Avatar
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??
Go4Expert Member
29Nov2006,15:46   #7
friendsforniraj's Avatar
good point shabbir
Go4Expert Founder
29Nov2006,16:17   #8
shabbir's Avatar
Quote:
Originally Posted by pradeep
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??
He edited the code to find a no is prime or not to loop till the sqrt(n) and not till n/2
Team Leader
29Nov2006,17:33   #9
pradeep's Avatar
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?
Go4Expert Founder
29Nov2006,18:00   #10
shabbir's Avatar
But 30 is the largets no. The smallest you will find is less than the sqrt(n).

For logic refer http://en.wikipedia.org/wiki/Prime_number Finding prime numbers section
Page 1 of 3
1
2
3