Sum of prime numbers in python

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

Write a program to find sum of all prime numbers between 1 to n.
Examples: 
 

Input : 10
Output : 17
Explanation : Primes between 1 to 10 : 2, 3, 5, 7.

Input : 11
Output : 28
Explanation : Primes between 1 to 11 : 2, 3, 5, 7, 11.

A simple solution is to traverse all numbers from 1 to n. For every number, check if it is a prime. If yes, add it to result.
An efficient solution is to use Sieve of Eratosthenes to find all prime numbers from till n and then do their sum.
 

C++

#include

using namespace std;

int sumOfPrimes(int n)

{

    bool prime[n + 1];

    memset(prime, true, n + 1);

    for (int p = 2; p * p <= n; p++) {

        if (prime[p] == true) {

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

                prime[i] = false;

        }

    }

    int sum = 0;

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

        if (prime[i])

            sum += i;

    return sum;

}

int main()

{

    int n = 11;

    cout << sumOfPrimes(n);

    return 0;

}

Java

import java.io.*;

import java.util.*;

class GFG {

    static int sumOfPrimes(int n)

    {

        boolean prime[]=new boolean[n + 1];

        Arrays.fill(prime, true);

        for (int p = 2; p * p <= n; p++) {

            if (prime[p] == true) {

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

                    prime[i] = false;

            }

        }

        int sum = 0;

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

            if (prime[i])

                sum += i;

        return sum;

    }

    public static void main(String args[])

    {

        int n = 11;

        System.out.print(sumOfPrimes(n));

    }

}

Python3

def sumOfPrimes(n):

    prime = [True] * (n + 1)

    p = 2

    while p * p <= n:

        if prime[p] == True:

            i = p * 2

            while i <= n:

                prime[i] = False

                i += p

        p += 1   

    sum = 0

    for i in range (2, n + 1):

        if(prime[i]):

            sum += i

    return sum

n = 11

print(sumOfPrimes(n))

C#

using System;

class GFG {

    static int sumOfPrimes(int n)

    {

        bool []prime=new bool[n + 1];

        for(int i = 0; i < n + 1; i++)

        prime[i] = true;

        for (int p = 2; p * p <= n; p++)

        {

            if (prime[p] == true)

            {

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

                    prime[i] = false;

            }

        }

        int sum = 0;

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

            if (prime[i])

                sum += i;

        return sum;

    }

    public static void Main()

    {

        int n = 11;

        Console.Write(sumOfPrimes(n));

    }

}

PHP

function sumOfPrimes($n)

{

    $prime = array_fill(0, $n + 1, true);

    for ($p = 2;

         $p * $p <= $n; $p++)

    {

        if ($prime[$p] == true)

        {

            for ($i = $p * 2;

                 $i <= $n; $i += $p)

                $prime[$i] = false;

        }

    }

    $sum = 0;

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

        if ($prime[$i])

            $sum += $i;

    return $sum;

}

$n = 11;

echo sumOfPrimes($n);

?>

Javascript

Output: 
 

28

Time Complexity: O(nloglogn)

Auxiliary Space: O(n)
This article is contributed by Rohit Thapliyal. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.