Sum of the first N Prime numbers
Given an integer ‘n’, the task is to find the sum of first ‘n’ prime numbers.
First few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, ……
Examples:
Input: N = 4 Output: 17 2, 3, 5, 7 are first 4 prime numbers so their sum is equal to 17 Input: N = 40 Output: 3087
Approach:
- Create a sieve which will help us to identify if the number is prime or not in O(1) time.
- Run a loop starting from 1 until and unless we find n prime numbers.
- Add all the prime numbers and neglect those which are not prime.
- Then, display the sum of 1st N prime numbers.
Below is the implementation of the above solution
C++
// C++ implementation of above solution #include <bits/stdc++.h> using namespace std; #define MAX 10000 // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. bool prime[MAX + 1]; void SieveOfEratosthenes() { memset (prime, true , sizeof (prime)); prime[1] = false ; for ( int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Set all multiples of p to non-prime for ( int i = p * 2; i <= MAX; i += p) prime[i] = false ; } } } // find the sum of 1st N prime numbers int solve( int n) { // count of prime numbers int count = 0, num = 1; // sum of prime numbers long long int sum = 0; while (count < n) { // if the number is prime add it if (prime[num]) { sum += num; // increase the count count++; } // get to next number num++; } return sum; } // Driver code int main() { // create the sieve SieveOfEratosthenes(); int n = 4; // find the value of 1st n prime numbers cout << "Sum of 1st N prime numbers are :" << solve(n); return 0; } |
Java
// Java implementation of above solution public class Improve { final static double MAX = 10000 ; // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. static boolean prime[] = new boolean [( int ) (MAX + 1.0 )] ; static void SieveOfEratosthenes() { for ( int i = 0 ; i <= MAX; i++) prime[i] = true ; prime[ 1 ] = false ; for ( int p = 2 ; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Set all multiples of p to non-prime for ( int i = p * 2 ; i <= MAX; i += p) prime[i] = false ; } } } // find the sum of 1st N prime numbers static int solve( int n) { // count of prime numbers int count = 0 , num = 1 ; // sum of prime numbers long sum = 0 ; while (count < n) { // if the number is prime add it if (prime[num]) { sum += num; // increase the count count++; } // get to next number num++; } return ( int ) sum; } // Driver code public static void main(String args[]) { // create the sieve SieveOfEratosthenes(); int n = 4 ; // find the value of 1st n prime numbers System.out.println( "Sum of 1st N prime numbers are :" + solve(n)); } // This Code is contributed by ANKITRAI1 } |
Python 3
# Python3 implementation of # above solution MAX = 10000 # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [ True for i in range ( MAX + 1 )] def SieveOfEratosthenes(): prime[ 1 ] = False for p in range ( 2 , MAX + 1 ): # If prime[p] is not changed, # then it is a prime if (prime[p] = = True ): # Set all multiples of # p to non-prime i = p * 2 while (i < = MAX ): prime[i] = False i = i + p # find the sum of 1st # N prime numbers def solve( n): # count of prime numbers count = 0 num = 1 # sum of prime numbers total = 0 while (count < n): # if the number is prime add it if ( prime[num] ): total = total + num # increase the count count = count + 1 # get to next number num = num + 1 return total # Driver code # create the sieve SieveOfEratosthenes() n = 4 # find the value of 1st # n prime numbers print ( "Sum of 1st N prime " + "numbers are :" , solve(n)) # This code is contributed by ash264 |
C#
//C# implementation of above solution using System; public class GFG{ static double MAX = 10000 ; // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. static bool []prime = new bool [( int )(MAX + 1.0)] ; static void SieveOfEratosthenes() { for ( int i = 0; i <= MAX; i++) prime[i] = true ; prime[1] = false ; for ( int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Set all multiples of p to non-prime for ( int i = p * 2; i <= MAX; i += p) prime[i] = false ; } } } // find the sum of 1st N prime numbers static int solve( int n) { // count of prime numbers int count = 0, num = 1; // sum of prime numbers long sum = 0; while (count < n) { // if the number is prime add it if (prime[num]) { sum += num; // increase the count count++; } // get to next number num++; } return ( int ) sum; } // Driver code static public void Main (){ // create the sieve SieveOfEratosthenes(); int n = 4; // find the value of 1st n prime numbers Console.WriteLine( "Sum of 1st N prime numbers are :" + solve(n)); } // This Code is contributed by ajit. } |
Javascript
<script> // javascript implementation of above solution var MAX = 10000 ; // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. var prime = Array.from({length: parseInt( (MAX + 1.0))}, (_, i) => false ); function SieveOfEratosthenes() { for (i = 0; i <= MAX; i++) prime[i] = true ; prime[1] = false ; for (p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Set all multiples of p to non-prime for (i = p * 2; i <= MAX; i += p) prime[i] = false ; } } } // find the sum of 1st N prime numbers function solve(n) { // count of prime numbers var count = 0, num = 1; // sum of prime numbers var sum = 0; while (count < n) { // if the number is prime add it if (prime[num]) { sum += num; // increase the count count++; } // get to next number num++; } return parseInt( sum); } // Driver code //create the sieve SieveOfEratosthenes(); var n = 4; // find the value of 1st n prime numbers document.write( "Sum of 1st N prime numbers are :" + solve(n)); // This code is contributed by 29AjayKumar </script> |
Output:
Sum of 1st N prime numbers are :17
Note(For competitive programming): In a problem which contains a large number of queries, a vector can be used to store all the prime numbers in the range of 10^8, this will take extra O(N) space. We can also use prefix array to store the sum of first N prime numbers in the range of 10^8.