Sum of all prime numbers between 1 and N ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )


 

Asked in Adobe and Samsung


Given a positive integer N, find the sum of all prime numbers between 1 and N(inclusive).

 

Example 1:

Input: N = 5
Output: 10
Explanation: 2, 3, and 5 are prime
numbers between 1 and 5(inclusive).

Example 2:

Input: N = 10
Output: 17
Explanation: 2, 3, 5 and 7 are prime
numbers between 1 and 10(inclusive).

 

Your Task:
You don't need to read or print anyhting. Your task is to complete the function prime_Sum() which takes N as input parameter and returns the sum of all primes between 1 and N(inclusive).
 

Expected Time Complexity: O(N*log(N))
Expected Space Complexity: O(N)

Constraints:
1 <= N <= 1000000


Code:


import java.util.*;

import java.lang.*;

import java.io.*;

class GFG

{

    public static void main(String[] args) throws IOException

    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine().trim());

        while(T-->0)

        {

            int n = Integer.parseInt(br.readLine().trim());

            Solution ob = new Solution();

            long ans = ob.prime_Sum(n);

            System.out.println(ans);

        }

    }

}

class Solution

{

    public long prime_Sum(int n)

    {

        long  s=0;

        if(n<=1)

           return 0;

         for(int i=2;i<=n;i++)

         {

             int c=2;

             for(int j=2;j*j<=i;j++)

             {

                 if(i%j==0)

                 {

                     c++;

                     break;

                 }

             }

if(c==2)

             {

                 s=s+i;

             }

         }

         return s;

    }

}

Previous
Next Post »