1. Home

Python Tutorials - Elevate Your Coding Skills with Comprehensive Tutorials

Discover Python tutorials covering everything from the basics to advanced topics. Whether you're new to programming or looking to level up your skills, our tutorials will guide you every step of the way

• 201 Lessons
• 33 Hours
190

# Sum of Prime Numbers in Python

Updated on 19/07/20246,696 Views

## Introduction

Diving deep into the Python ecosystem unveils a myriad of tools and techniques to tackle complex problems. In this tutorial, we'll specifically focus on how professionals can compute the sum of prime numbers in Python. Whether you're prepping for a challenging coding interview or trying to solve an intricate algorithmic task, this tutorial promises to equip you with the knowledge to handle prime-related calculations with ease.

## Overview

Python, a prominent name in the programming sphere, encapsulates simplicity and power. As we journey through this tutorial, we'll utilize the built-in functionalities and optimized techniques to efficiently come up with the sum of prime numbers in Python, a fundamental concept in the realm of number theory and algorithms.

## Defining Prime Numbers

Prime numbers are a central subject of study in the mathematical world, often serving as the backbone of number theory and intricate computational algorithms. They've fascinated mathematicians since ancient times and have often been the focal point of many groundbreaking mathematical discoveries.

To put it simply, prime numbers are those distinct integers greater than one that can't be formed by multiplying two smaller natural numbers. They do not have any divisors in between. This unique nature of prime numbers has been crucial in various applications ranging from ancient cryptosystems to modern-day digital encryption methodologies. Furthermore, their recurrent yet unpredictable patterns pose interesting questions and have inspired countless research projects.

Apart from their inherent indivisibility, prime numbers possess some intriguing attributes:

1. Uniqueness: Every prime number is unique.
2. Primordial Position: The number 2 has a special place as it is the first and only even prime number.
3. Oddity: Barring 2, all prime numbers are odd, since even numbers can always be divided by 2.

To better delineate between prime and non-prime (composite) numbers, consider the table below:

 Number Type Definition Example Numbers Prime Only divisible by 1 and itself 3, 5, 7 Composite Divisible by numbers other than 1 & itself 4, 6, 8

Examples for Sum of Prime Numbers in Python in Any Given Range

### Method #1: Naive Approach

This program will demonstrate how to calculate the sum of prime numbers within a specified range using a relatively simple primality testing function. While effective, this approach may not be the most efficient for larger ranges.

`def is_prime(num):    if num <= 1:        return False    if num <= 3:        return True    if num % 2 == 0 or num % 3 == 0:        return False    i = 5    while i * i <= num:        if num % i == 0 or num % (i + 2) == 0:            return False        i += 6    return Truedef sum_of_primes_in_range(start, end):    prime_sum = 0    for num in range(start, end + 1):        if is_prime(num):            prime_sum += num    return prime_sum`
`# Example usagestart_range = 10end_range = 50result = sum_of_primes_in_range(start_range, end_range)print(f"Sum of prime numbers between {start_range} and {end_range} is: {result}")`

Explanation:

is_prime(num) function: This function checks whether a given number num is prime using a simple primality testing approach.

• If num is lesser than or equal to 1, it returns False as prime numbers are greater than 1.
• If num is 2 or 3, it returns True as both 2 and 3 are prime.
• If num is divisible by 2 or 3, it returns False, excluding even numbers and numbers divisible by 3.
• It initializes i to 5 and enters a loop that continues as long as i * i is less than or equal to num.
• Within the loop, it checks if num is divisible by i or i + 2. If so, it returns False.
• The value of i is incremented by 6 in each iteration to efficiently check divisibility for numbers that are 6 units apart.
• If no divisors are found within the loop, the function returns True, indicating that the number is prime.

sum_of_primes_in_range(start, end) function: This function calculates the sum of prime numbers within a given range from start to end.

• It initializes prime_sum to 0, which will store the cumulative sum of prime numbers.
• It iterates through each number in the range from start to end (inclusive).
• For each number, it calls the is_prime function to check if it's prime.
• If the number is prime (i.e., is_prime(num) returns True), it adds the number to prime_sum.
• After iterating through all numbers in the specified range, the function returns the calculated prime_sum.

Example Usage:

• The code sets start_range to 10 and end_range to 50.
• It calls the sum_of_primes_in_range function with these range values and stores the result in the variable result.
• Finally, it prints a formatted string indicating the sum of prime numbers between the start_range and end_range.

### Method #2: Optimised Sieve of Eratosthenes

The code below will demonstrate how to calculate the sum of prime numbers within a specified range using the Sieve of Eratosthenes algorithm. This algorithm is efficient for generating prime numbers and is utilized here to mark non-prime numbers within the range, leading to the calculation of the sum of prime numbers.

`def sum_of_primes_in_range(start, end):    is_prime = [True] * (end + 1)    is_prime[0] = is_prime[1] = False    for num in range(2, int(end**0.5) + 1):        if is_prime[num]:            for multiple in range(num*num, end + 1, num):                is_prime[multiple] = False    prime_sum = sum(num for num in range(start, end + 1) if is_prime[num])    return prime_sum# Example usagestart_range = 10end_range = 50result = sum_of_primes_in_range(start_range, end_range)print(f"Sum of prime numbers between {start_range} and {end_range} is: {result}")`

Explanation:

sum_of_primes_in_range(start, end) function: This function calculates the sum of prime numbers within a given range from start to end.

• It starts by creating a boolean list is_prime of size end + 1, where each index represents a number and the value at that index indicates whether the number is prime or not.
• It sets the values at indices 0 and 1 to False since 0 and 1 are not prime.
• It then iterates through the numbers from 2 to the square root of end using the num variable.
• If the value at is_prime[num] is True, it means num is prime, so it proceeds to mark its multiples as False in the is_prime list. This is the core of the Sieve of Eratosthenes algorithm.
• After marking non-prime numbers, the function calculates the sum of prime numbers within the specified range using a generator expression and the sum function.
• Finally, it returns the calculated sum of prime numbers.

Example Usage:

• The code sets start_range to 10 and end_range to 50.
• It calls the sum_of_primes_in_range function with these range values and stores the result in the variable result.
• Finally, it prints a formatted string indicating the sum of prime numbers between the start_range and end_range.

### Method #3: Dynamic Programming

We will use the example below to demonstrate an efficient approach to calculating the sum of prime numbers using the Sieve of Eratosthenes algorithm and dynamic programming to store cumulative prime sums.

`import math n = 1000dp = [0] * (n + 1)def sieve():a = [0] * (n + 1)a[0] = 1a[1] = 1for i in range(2, math.ceil(math.sqrt(n) + 1)):if a[i] == 0:for j in range(i * i, n + 1, i):a[j] = 1PrimeSum = 0for i in range(1, n + 1):if a[i] == 0:PrimeSum += idp[i] = PrimeSuml = 4r = 13sieve()print(dp[r] - dp[l - 1])`

Explanation:

1. The code begins by importing the math module, which provides mathematical functions.

2. It sets the value of n to 1000, which is the upper limit for the range of numbers being considered.

3. It initializes a list called dp of size (n + 1) with all elements set to 0. This list will be used for dynamic programming to store the cumulative sums of prime numbers.

4. The sieve() function is defined to implement the Sieve of Eratosthenes algorithm:

• It creates a list of size (n + 1) to keep track of whether a number is prime or not. It initializes elements at indices 0 and 1 to 1 since 0 and 1 are not prime.
• It iterates through numbers from 2 to the square root of n, and if a[i] is 0 (indicating that i is prime), it marks the multiples of i as 1 in the list a. This is the sieve step of the algorithm.
• The PrimeSum variable is initialized to 0.
• It iterates through numbers from 1 to n, and if a[i] is 0 (indicating that i is prime), it adds i to PrimeSum and stores the value of PrimeSum in the corresponding index of the dp list.

5. After defining the sieve() function, the code sets the values of l to 4 and r to 13, indicating the range of numbers for which the sum of prime numbers is to be calculated.

6. The sieve() function is called to populate the dp list with cumulative prime sums.

7. Finally, the code prints the difference between the cumulative prime sum at index r and the cumulative prime sum at index l - 1. This effectively calculates the sum of prime numbers within the range [l, r].

## Sum of Prime Numbers Using the Miller-Rabin Primality Test Method in Python

The Miller-Rabin primality test is a probabilistic algorithm used to determine if a given number is likely to be prime. Here's an example of how you could use the Miller-Rabin primality test to calculate the sum of prime numbers within a given range in Python:

import random

`def power(x, y, p):    result = 1    x = x % p    while y > 0:        if y % 2 == 1:            result = (result * x) % p        y = y // 2        x = (x * x) % p    return resultdef is_prime_miller_rabin(n, k=5):    if n <= 1:        return False    if n <= 3:        return True    if n % 2 == 0:        return False    d = n - 1    while d % 2 == 0:        d //= 2    for _ in range(k):        a = random.randint(2, n - 2)        x = power(a, d, n)        if x == 1 or x == n - 1:            continue        for _ in range(d - 1):            x = (x * x) % n            if x == n - 1:                break        else:            return False    return Truedef sum_of_primes_in_range(start, end):    prime_sum = sum(num for num in range(start, end + 1) if is_prime_miller_rabin(num))    return prime_sum# Example usagestart_range = 10end_range = 50result = sum_of_primes_in_range(start_range, end_range)print(f"Sum of probable prime numbers between {start_range} and {end_range} is: {result}")`

The Miller-Rabin primality test is probabilistic, meaning that it can sometimes give false positives for composites. The accuracy of the test increases with the number of iterations (k), so you can adjust the value of k to balance between accuracy and efficiency.

## Conclusion

Harnessing Python to compute the sum of prime numbers elucidates the language's versatility and efficiency. For professionals endeavoring to dominate the coding world, understanding such nuanced topics is invaluable. If this exploration ignited a thirst for deeper Python knowledge, remember: upGrad offers meticulously curated courses to refine your skills. Elevate your coding journey and make a mark in the tech industry by taking a strategic plunge into upGrad's educational reservoir.

## FAQs

1. Does Python have built-in functions for prime operations?

While Python doesn't offer direct built-in functions for prime checks, its powerful library system, like SymPy, provides tools for prime operations.

2. How can we optimize the prime check in Python?

Using the square root method for iteration limits and employing the Sieve of Eratosthenes for larger numbers can optimize the process.

3. What's the relevance of the sum of first n prime numbers in real-world applications?

It's valuable in areas like cryptography, digital signatures, and coding theory, emphasizing the importance of prime numbers.

4. Is the sum of prime numbers Python finite?

No, according to Euclid's theorem, there are infinitely many prime numbers. Hence, the sum of all prime numbers is infinite.

5. Can the sum of prime numbers formula be used in other programming languages?

The concept is universal, but the implementation varies based on the language's syntax and available libraries.

Director of Engineering

Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working …Read More

###### Need More Help? Talk to an Expert
+91
*
By clicking, I accept theT&Cand
Join 10M+ Learners & Transform Your Career
Learn on a personalised AI-powered platform that offers best-in-class content, live sessions & mentorship from leading industry experts.

Talk to our experts. We’re available 24/7.

Indian Nationals

1800 210 2020

Foreign Nationals

+918045604032

## Disclaimer

upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enr...