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?**

Submitted by Bipin Kumar, on October 25, 2019

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.

**Code:**

N=1000 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 sum of prime numbers: 76127

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions