Sum of Prime Numbers in Python

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:

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 True

def 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 usage
start_range = 10
end_range = 50
result = 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 usage
start_range = 10
end_range = 50
result = 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 = 1000
dp = [0] * (n + 1)
def sieve():
a = [0] * (n + 1)

a[0] = 1
a[1] = 1
for 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] = 1

PrimeSum = 0
for i in range(1, n + 1):
if a[i] == 0:
PrimeSum += i
dp[i] = PrimeSum
l = 4
r = 13
sieve()
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 result

def 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 True

def 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 usage
start_range = 10
end_range = 50
result = 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.