Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Find the sum of all the prime numbers (http://www.go4expert.com/articles/sum-prime-t2049/)

pradeep 29Nov2006 10:28

Find the sum of all the prime numbers
 
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);
 }


friendsforniraj 29Nov2006 15:06

Re: Find the sum of all the prime numbers
 
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

pradeep 29Nov2006 15:33

Re: Find the sum of all the prime numbers
 
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.

shabbir 29Nov2006 15:36

Re: Find the sum of all the prime numbers
 
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

friendsforniraj 29Nov2006 15:41

Re: Find the sum of all the prime numbers
 
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.

pradeep 29Nov2006 15:41

Re: Find the sum of all the prime numbers
 
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??

friendsforniraj 29Nov2006 15:46

Re: Find the sum of all the prime numbers
 
good point shabbir

shabbir 29Nov2006 16:17

Re: Find the sum of all the prime numbers
 
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

pradeep 29Nov2006 17:33

Re: Find the sum of all the prime numbers
 
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?

shabbir 29Nov2006 18:00

Re: Find the sum of all the prime numbers
 
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

shabbir 29Nov2006 18:02

Re: Find the sum of all the prime numbers
 
There is other method also which does not require sqrt.

Quote:

Originally Posted by wiki
One need not actually calculate the square root; once one sees that the quotient is less than the divisor, one can stop


pradeep 29Nov2006 18:16

Re: Find the sum of all the prime numbers
 
Interesting, so we will find the factor of n within any of the number in sqrt(n) if not then its a prime number.

friendsforniraj 2Dec2006 17:57

Re: Find the sum of all the prime numbers
 
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

shabbir 4Dec2006 10:45

Re: Find the sum of all the prime numbers
 
friendsforniraj thats a good logic explained.

friendsforniraj 5Dec2006 17:40

Re: Find the sum of all the prime numbers
 
thank u sir
but ma name is niraj

shabbir 6Dec2006 11:13

Re: Find the sum of all the prime numbers
 
Quote:

Originally Posted by friendsforniraj
thank u sir
but ma name is niraj

I will try putting that from now on.

rahul.mca2001 6Mar2008 13:53

Re: Find the sum of all the prime numbers
 
why do we need a square root

asadullah.ansari 7Mar2008 20:19

Re: Find the sum of all the prime numbers
 
Quote:

Originally Posted by friendsforniraj
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

Excellent explaination. Now any one can understand either he is new or experience

oleber 8Mar2008 12:51

Re: Find the sum of all the prime numbers
 
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.

oleber 8Mar2008 12:54

Re: Find the sum of all the prime numbers
 
for getting the prime number try

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

No devisions in here

rai_gandalf 8Apr2008 22:11

Re: Find the sum of all the prime numbers
 
Its wonderful how such an apparently trivial problem of finding prime numbers is turning into such an animated discussion on various algorithmic techniques - each with its own benefits & pitfalls!

Wikipedia's page on the prime number is as exhaustive as its page on human evolution! It just goes to show how fascinating Mathematics is that it throws a challenge in something as apparently simple as finding primes.

It also demonstrates the importance of algorithmic design & analysis for effective computing - even the biggest super-computer on the planet cannot achieve its true computational potential if the algorithm involves excessive looping or is inefficient!

Also, a special thanks to Niraj (friendsofniraj), who has given an extremely succint explanation of how the Square Root logic works - there was no need for me to read a single word on Wiki about the algorithm (although I did to satiate my curiosity - and might I say, it is very thoroughly dissected in Wikipedia!) And also the keen eye of Shabbir noticed the redundancy in the calculation of Square Root through the inner-loop!

All in all - a very fascinating discussion!

Regards,
Rajiv


All times are GMT +5.5. The time now is 06:37.