Sum of Prime Numbers in Python

Introduction

Before starting with the algorithm where we shall understand how to find the sum of all prime numbers between 1 to n, we should first briefly understand what prime numbers are.

A prime number can be defined as a positive integer greater than 1 and only divisible by two numbers, 1 and itself.

To find the prime numbers with python, please go through the article Prime Number Program in Python as this covers the basic to advanced level of how we can find the prime numbers in python along with few programs of optimizing that code.

After you have gone through the above article, let us discuss the algorithm we will follow to find the sum of prime numbers in python.

Step1: As we are looking to find the sum of prime numbers up to N, we first need to iterate through each number up to the given number. Step2: Then, we check if the given number is a prime or not. We can add and store it in a temporary variable if it is a prime number. Step3: Now, as the outer loop is completed, we can get the sum of primes by printing the temporary variable.

As explained above, we can now move on to understand the program to find the sum of prime numbers in python as below. We cover two specific approaches: the simple approach and the Sieve of Eratosthenes approach. Both approaches are easy to understand, the only difference being that the Sieve of Eratosthenes approach is more efficient.

Python Program to Find Sum of All Prime Numbers Between 1 to n.

Let us understand the simple approach to finding the sum of prime numbers in python.

We traverse all the numbers from 1 to n in this approach. Then, we check every number to see if it is a prime. If the number is prime, we add it to the output.

It is a very basic and easier approach to solving our problem statement.

Code:

Output:

Explanation:

Here we started with the input from the user, where we take the number till which the sum of prime numbers in python needs to be known. Then we use for loop in python to iterate for each number starting from 2. As known, the first prime number is 2, so we started the for loop with it.

Now, we iterate each number to check if it is a prime number or not. We do so by evaluating it and analyzing the remainder as not equal to zero. Then we take that number and continue adding to the previously added prime numbers.

In the end, we print the sum of all the primes up to the last number as input by the user.

Python Program to Find the Sum of All Prime Numbers Between 1 to n using Sieve of Eratosthenes

Let us understand the Sieve of Eratosthenes approach to finding the sum of prime numbers in python. The Sieve of Eratosthenes is said to be an efficient method to calculate the sum of prime numbers in python. In this approach, we find all the prime numbers until the last number. Once we have all the prime numbers, we find the addition of them.

Now, let us understand the algorithm to see how to find all the prime numbers that are less than or equal to a given integer n by the Sieve of Eratosthenes method. It is important to note that once the algorithm terminates, all the numbers not marked in the list are prime numbers.

Explanation: Consider an example where n = 40. Now we need to print all the prime numbers that are smaller than or equal to 40. For the same, we create a list of all the numbers from 2 to 40, as seen below.

As described above in the algorithm, we shall now mark all the numbers that are divisible by 2. We start marking all the numbers that are multiples of 2. Also, these numbers need to be greater than or equal to the square of it, as seen below.

We see that there are many unmarked numbers. We now move to the next unmarked number, 3. We start marking all the numbers that are multiples of 3. Also, these numbers need to be greater than or equal to the square of it, as seen below.

We repeat the same process. We now move to the next unmarked number, that is, 5. We start marking all the numbers that are multiples of 5. Also, these numbers need to be greater than or equal to the square of it, as seen below.

We continue the same process, and the final table shall look like this as seen below:

The prime numbers which are unmarked are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.

Now, as we understand how to use the Sieve of Eratosthenes concept, let us dive deep into the program to find the sum of prime numbers in python.

Code:

Output:

Explanation: Here we have applied the same logic we just explained above. We first create the function Sum_Of_Primes, then we check each number and evaluate if it is a prime or not. Once we check if the number is a prime number or not for all the numbers till n, we then collect all the prime numbers. Now we add all the prime numbers and print the output.

See Also:

• Factorial Program in Python.
• Factorial Using Recursion in Python.
• FizzBuzz Program in Python.
• Sum of Digits of a Number in Python.
• Sum of n natural numbers in python.