Home »
Python »
Python Programs
Find the sum of all prime numbers in Python
Here, we are going to learn how to find the sum of all prime numbers till 1000 in Python programming language?
By Bipin Kumar Last updated : January 05, 2024
Solution overview
To do this task, we will use the Sieve of Eratosthenes which is one of the most famous algorithms of Python language which is used to find prime numbers. No need to worry about it that one thousand is the large number and how we will find the all Prime number less than one thousand. So, before going to solve this problem in the easiest way we will learn a little bit about what is Sieve of Eratosthenes and it's algorithm how applicable in our task.
Sieve of Eratosthenes and its algorithm
It is a simple and ancient method for finding all Prime numbers less than or equal to N and here the value of N is one thousand.
Algorithm to find the sum of Prime numbers less than or equal to one thousand by Sieve of Eratosthenes,
- We create a boolean array of size equal to the given number (N) and mark each position in the array True.
- We initialize a variable p equal to 2 and s equal to 0.
- If the variable p is prime then mark each multiple of number False in the array.
- Update the variable p by an increment of 1 i.e p = p+1.
- Repeat step 2 until the square of the variable is less than the given number (N).
- The elements in the array with True contain all Prime numbers less than or equal to the given number and the elements of the array which is our Prime number.
- After the above process, we will simply find the sum of the prime numbers.
Let's start writing a Python program using the above algorithm in a simple way.
Python program to find the sum of all prime numbers
# input the value of N
N = int(input("Input the value of N: "))
s = 0 # variable s will be used to find the sum of all prime.
Primes = [True for k in range(N + 1)]
p = 2
Primes[0] = False # zero is not a prime number.
Primes[1] = False # one is also not a prime number.
while p * p <= N:
if Primes[p] == True:
for j in range(p * p, N + 1, p):
Primes[j] = False
p += 1
for i in range(2, N):
if Primes[i]:
s += i
print("The sum of prime numbers:", s)
Output
The output of the above example is:
Test case 1:
Input the value of N: 10
The sum of prime numbers: 17
Test case 2:
Input the value of N: 100
The sum of prime numbers: 1060
Test case 3:
Input the value of N: 1000
The sum of prime numbers: 76127
To understand the above program, you should have the basic knowledge of the following Python topics:
Python Basic Programs »