Sum of Prime Numbers in Python

A prime number in Python is a number greater than 1 that has no divisors other than 1 and itself. Examples of prime numbers are 2, 3, 5, 7, and so on.  

You’ll look at how the sum of prime numbers in Python using for loop, and other techniques.  It can be tricky to check if a number is prime, especially when you want to sum a series of prime numbers efficiently. 

By the end of this article, you will be able to calculate sum of n prime numbers in Python boosting your understanding of loops and prime number logic in Python. 

“Enhance your Python skills further with our Data Science and Machine Learning courses from top universities — take the next step in your learning journey!”

Find the Sum of All Prime Numbers Using For Loop

Let’s look at how to calculate the sum of prime numbers in Python using a for loop.  

def is_prime(num):
    if num <= 1:
        return False  # Numbers less than or equal to 1 are not prime
    for i in range(2, int(num ** 0.5) + 1):  # Check divisibility up to the square root of num
        if num % i == 0:
            return False  # If num is divisible by i, it's not prime
    return True  # If no divisors are found, num is prime
# Sum of prime numbers up to n
n = int(input("Enter a number: "))  # Take user input for n
sum_primes = 0  # Initialize sum variable
# Loop to check each number up to n
for i in range(2, n + 1):  # Start from 2, since 1 is not a prime number
    if is_prime(i):  # Check if the current number i is prime
        sum_primes += i  # Add prime number to the sum
print(f"Sum of prime numbers between 1 and {n} is: {sum_primes}")

Output: 

Enter a number: 10Sum of prime numbers between 1 and 10 is: 17

Explanation:

• is_prime(num) function:
• • This function checks if a given number num is prime.
  • Base case: If num is less than or equal to 1, it returns False because 1 is not a prime number.
  • Divisibility check: The loop runs from 2 to the square root of num. If num is divisible by any number in this range, it's not prime, and the function returns False.
  • If no divisors are found, the function returns True, indicating that num is prime.
• sum_primes = 0:
• • We initialize a variable sum_primes to 0, which will store the cumulative sum of prime numbers.
• for i in range(2, n + 1):
• • The loop starts from 2 because 1 is not a prime number, and iterates through all numbers from 2 up to n.
  • Inside the loop, we check if i is prime by calling the is_prime(i) function.
• sum_primes += i:
• • If i is prime, we add it to the sum_primes variable.
• Final Output:
• • Once the loop completes, we print the total sum of prime numbers between 1 and n.

Why Use a For Loop?

Using a for loop is an intuitive and straightforward approach when you want to check each number in a sequence. This method allows you to break down the task into manageable steps—checking each number and summing the primes efficiently.

This approach works well for relatively smaller values of n where performance is not a critical concern. However, as the value of n grows, this approach can become slower because it checks each number individually.

When to Use This Method

• Use the sum of prime numbers in Python using for loop when:
• • You are dealing with smaller values of n.
  • You prefer an easy-to-understand approach for prime number summation.

“Start your coding journey with our complimentary Python courses designed just for you — dive into Python programming fundamentals, explore key Python libraries, and engage with practical case studies!”

Find the Sum of All Prime Numbers Using Sieve of Eratosthenes

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a given number n. This method is especially useful when you need to find multiple primes and calculate their sum, as it eliminates non-prime numbers in an efficient manner. 

Let’s look at how to calculate the sum of prime numbers in Python using the Sieve of Eratosthenes.

# Function to calculate sum of prime numbers using Sieve of Eratosthenes
def sieve_of_eratosthenes(n):
    # Step 1: Create a boolean array "prime[0..n]" and initialize all entries as True.
    # A value in prime[i] will be False if i is Not a prime, True if i is a prime.
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False  # 0 and 1 are not prime numbers
    # Step 2: Implement the Sieve of Eratosthenes algorithm
    for p in range(2, int(n**0.5) + 1):  # Check only up to the square root of n
        if prime[p]:  # If prime[p] is still True, it is a prime number
            for i in range(p * p, n + 1, p):  # Mark multiples of p as non-prime
                prime[i] = False
    # Step 3: Calculate the sum of primes
    prime_sum = sum(i for i in range(2, n + 1) if prime[i])  # Sum all prime numbers
    return prime_sum
# Take user input for n
n = int(input("Enter a number: "))
# Call the function and print the result
result = sieve_of_eratosthenes(n)
print(f"Sum of all prime numbers up to {n} is: {result}")

Output: 

Enter a number: 10Sum of all prime numbers up to 10 is: 17

Explanation:

• Prime Array Initialization:
• • prime = [True] * (n + 1): We create a list of boolean values representing whether each number from 0 to n is prime or not. Initially, all numbers are assumed to be prime (True).
  • prime[0] = prime[1] = False: We manually mark 0 and 1 as non-prime because by definition, they aren't prime numbers.
• Sieve Algorithm:
• • The for p in range(2, int(n**0.5) + 1) loop iterates over numbers starting from 2 up to the square root of n. We only need to check for divisibility up to the square root of n, as factors above the square root would already have corresponding smaller factors.
  • If prime[p] is True, it means p is a prime number, and we mark all multiples of p as non-prime (prime[i] = False).
• Summing Primes:
• • prime_sum = sum(i for i in range(2, n + 1) if prime[i]): After applying the sieve, this line sums up all the indices that are still marked as True (indicating they are prime).
• Final Output:
• • The program calculates the sum of all primes up to n and prints the result.

Why Use the Sieve of Eratosthenes?

The Sieve of Eratosthenes is much more efficient than using a for loop for checking each number individually. The algorithm works in O(n log log n) time complexity, making it far more suitable for larger values of n compared to methods that check each number's primality individually, which can take O(n * sqrt(n)) time.

Find the Sum of All Prime Numbers Using the Miller-Rabin Primality Test Method

The Miller-Rabin primality test is an efficient probabilistic algorithm used to check if a number is prime. Unlike the Sieve of Eratosthenes, which finds all primes up to n, the Miller-Rabin test is used for testing the primality of individual numbers. 

It is particularly useful when dealing with large numbers due to its efficiency. 

The Miller-Rabin primality test is a probabilistic algorithm, which means it can occasionally produce a false positive. However, by running the test multiple times, we can reduce the probability of such errors. It works by checking if a number passes certain conditions that hold for prime numbers. 

Here is the Python code to find the sum of prime numbers in Python: 

import random
# Miller-Rabin primality test function
def miller_rabin(n, k=5):
    # Handle small cases
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # Write n-1 as d*2^r
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    # Test for primality k times
    for _ in range(k):
        a = random.randint(2, n - 2)  # Choose a random base a
        x = pow(a, d, n)  # Compute a^d % n
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)  # Compute x^2 % n
            if x == n - 1:
                break
        else:
            return False  # Return false if no prime is found
    return True
# Sum of prime numbers up to n
def sum_of_primes(n):
    sum_primes = 0
    for i in range(2, n + 1):  # Loop through numbers from 2 to n
        if miller_rabin(i):  # Check if the number is prime
            sum_primes += i  # Add prime number to the sum
    return sum_primes
# Take user input for n
n = int(input("Enter a number: "))
# Calculate sum of prime numbers using Miller-Rabin test
result = sum_of_primes(n)
print(f"Sum of all prime numbers up to {n} using Miller-Rabin test is: {result}")

Output: 

Enter a number: 10Sum of all prime numbers up to 10 using Miller-Rabin test is: 17

Explanation:

• Miller-Rabin Primality Test:
• • The function miller_rabin(n, k) checks if a number n is prime by performing k iterations of the test. Each iteration involves choosing a random base a, calculating a^d % n, and checking certain conditions to determine primality.
  • Base Case: If n <= 1, the number is not prime. If n == 2, the number is prime. If n is even, it is not prime.
  • The number is expressed as n-1 = d * 2^r. The test checks if a^d % n equals 1 or n-1 and performs additional checks for non-trivial square roots modulo n.
• Summing Primes:
• • sum_of_primes(n) iterates through each number from 2 to n, checking if each number is prime using the miller_rabin(i) function. If the number is prime, it is added to the sum_primes variable.
• Final Output:
• • After the loop completes, the sum of all prime numbers up to n is printed. For example, the sum of prime numbers up to 10 is 17, since the primes are 2, 3, 5, and 7.

Why Use the Miller-Rabin Primality Test?

The Miller-Rabin primality test is much faster than traditional methods for large numbers because it avoids checking every possible divisor. While it is a probabilistic test, it’s very efficient and can be made extremely accurate by running the test multiple times (adjustable with the k parameter).

This method is particularly useful for:

• Large number primality testing: When you need to check the primality of very large numbers, such as in cryptography or number theory.
• Efficiency: The Miller-Rabin test is faster for large values of n compared to traditional for loop methods of checking divisibility.

Also Read: Perfect Number Program In Python: How to check if a number is perfect or not?

FAQs

1. What is the sum of prime numbers in Python using for loop?

The sum of prime numbers in Python using for loop refers to the process of iterating through numbers, checking if they are prime, and summing the prime numbers found.

2. How can I calculate the sum of n prime numbers in Python?

To calculate the sum of n prime numbers in Python, you can use a for loop to check if each number from 2 to n is prime and add them to the sum.

3. What is the Miller-Rabin primality test?

The Miller-Rabin primality test is a probabilistic algorithm used to determine if a number is prime. It is more efficient for larger numbers compared to traditional primality tests.

4. How do I find the sum of prime numbers in Python using the Sieve of Eratosthenes?

The Sieve of Eratosthenes finds all primes up to n by iterating through numbers and marking the multiples of each prime as non-prime. You can sum the primes found in this way.

5. Can I use the sum of n prime numbers in Python with recursion?

Yes, you can use recursion to check if a number is prime and calculate the sum of n prime numbers in Python by recursively summing primes up to n.

6. What is the time complexity of the Miller-Rabin test for large numbers?

The Miller-Rabin test runs in O(k log n) time complexity, where k is the number of iterations. This makes it much faster than traditional primality testing for large numbers.

7. How does the for loop method for prime number summation compare to other methods?

The for loop method is straightforward but slower for large n compared to optimized methods like the Sieve of Eratosthenes or Miller-Rabin primality test.

8. Is the Sieve of Eratosthenes method more efficient than the for loop method?

Yes, the Sieve of Eratosthenes is more efficient for finding multiple primes up to n because it avoids checking each number individually, unlike the sum of prime numbers in Python using for loop.

9. Can the Miller-Rabin test return false positives?

Yes, the Miller-Rabin test is probabilistic, meaning it can return false positives. However, increasing the number of iterations reduces this probability.

10. Which method is the best for finding the sum of prime numbers in Python?

For small n, the sum of prime numbers in Python using for loop works fine. For larger values, the Sieve of Eratosthenes or Miller-Rabin test is more efficient. Choose based on the problem size.

11. What is the difference between checking prime numbers using for loop and using the Miller-Rabin test?

The for loop method checks divisibility for each number, making it slower for large n. The Miller-Rabin test is a faster, probabilistic method for checking primality, especially with large numbers.

Take our Free Quiz on Python

Answer quick questions and assess your Python knowledge

Start Quiz