Sum of Prime Numbers in Python

Overview

Prime numbers are natural numbers that are divisible by only one and the number itself. In other words, prime numbers are positive integers greater than 1 with exactly two factors, one and the number itself. Some prime numbers include 2, 3, 5, 7, 11, 13, etc. And the sum of prime numbers denotes the summation of all the prime numbers less than or equal to the given input.

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 Eratosthenesis 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.

Conclusion

• To get a fair idea of finding the prime number in python is explained in Prime Number Program in Python, and the user is advised to go through it first before starting this module.

• The algorithm to find the sum of prime numbers in python is as follows:

Step1: We first need to iterate through each number up to the given number.

Step2: We check if the given number is a prime or not. If it is a prime number, we can easily find the addition of the numbers and store it in a temporary variable.
Step3: We can get the sum of all primes by printing the temporary variable.

• 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.

• The Sieve of Eratosthenesis an efficient method to calculate the sum of prime numbers in python as we first find all the prime numbers till the last number. Once we have all the prime numbers, we find the addition of them.

You are watching: Sum of Prime Numbers in Python. Info created by GBee English Center selection and synthesis along with other related topics.