Sum of prime numbers in the input in python using def

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.

Scope

• The module assumes the user to be well versed with the basics of python.
• The user of this manual should also go through the module Prime Number Program in Python before starting to code for the sum of prime numbers in python.
• The two approaches covered include the simple and the most efficient approach, the Sieve of Eratosthenes approach.
• A fair idea of what prime numbers are and how we can find the prime number in python is explained in brief. For in-depth understanding, the user is advised to go through Prime Number Program 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 be following 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 are covering two specific approaches: the simple approach and the Sieve of Eratosthenes approach. Both the approach 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.

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

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

Code:

# Start by taking an input of number from user

Last_number = int(input("\nPlease enter the last number uptill which sum of prime number is to be found:"))
print ("\nWe will find the sum of prime numbers in python upto" , Last_number)
sum = 0
# Initializing the sum to 0
for number in range(2, Last_number + 1):
# Using for loop starting from 2 as its the first prime number.
    i = 2
    for i in range(2, number):
        if (int(number % i) == 0):
            i = number
            break;
#Only if the number is prime number, then continue to add it.
    if i is not number:
        sum = sum + number
print("\nThe sum of prime numbers in python from 1 to ", Last_number, " is :", sum)

Output:

Please enter the last number uptill which sum of prime number is to be found: 60
We will find the sum of prime numbers in python upto 60
The sum of prime numbers in python from 1 to  60  is : 438

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 to not be 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 given as an input by the user.

Python Program to Find 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 first find all the prime numbers till the last number. Once we have all the prime numbers, we then find the addition of all 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 here that once the algorithm terminates, then all the numbers that are not marked in the list are the 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 also 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 also 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 also 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 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 we are going to use the Sieve of Eratosthenes concept, let us dive deep into the program to find the sum of prime numbers in python.

Code:

# To find the sum of prime number in python from range 2 to n.

# Defining the function 
def Sum_Of_Primes(n):
# creating a list to store the prime numbers
	prime = [True] * (n + 1)
	
# We have created a boolean array "prime[0..n]".
# We initialize all the entries as true.
# Logic : The value in prime[i] if is prime it will be True, else False. 
	
	s = 2
# As the prime numbers start from 2.
	while s * s <= n:
# If the prime[s] is not changing, then it is a prime hence TRUE.
		if prime[s] == True:
# We update all the multiples of s if the prime is TRUE.
			i = s * 2
			while i <= n:
				prime[i] = False
				i += s
		s = s + 1
		
# We return the sum of primes generated through the Sieve of Eratosthenes.
	sum = 0
	for i in range (2, n + 1):
		if(prime[i]):
			sum = sum + i
	return sum

n = int(input("\nPlease enter the last number up to which sum of prime number is to be found:"))
print("\n The sum of prime numbers in python from 1 to " , n, "is : ",Sum_Of_Primes(n))

Output:

Please enter the last number up to which sum of the prime number is to be found:40
The sum of prime numbers in python from 1 to  40 is:  197

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 [https://www.scaler.com/topics/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 then 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 if it is a prime or not. 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.