Algorithm and Flowchart to represent a number as sum of two prime numbers

[1660 views]

What are prime numbers?

A number is said to be a prime number when it has only two factors, that is, when the factors of the number are 1 and the number itself. Example: 2, 5, 17, 19, etc.

Sum of Prime Numbers:

There are many theories which state that any number greater than 2 can be expressed as the sum of two prime numbers. We must also keep in mind that the sum of two prime numbers does not necessarily have to be a prime number. In this article, we will check whether a given number can be displayed as the sum of two prime numbers.

For example:
15 = 2 + 13
25 = 2 + 23

Now let’s take a look at the algorithm and flowchart to check whether two given numbers are twin prime or not, for better understanding.

Algorithm to represent a given number as the sum of two prime numbers:

To avoid redundancy, we will use the concept of functions. Here, we will use a function to check whether a number is prime or not. While writing the program, we can call this function any number of times we want.

CheckPrime(num):

Assumption: For this algorithm, we assume that the function takes a number ‘num’, to be checked and returns true if the number is prime, otherwise, returns false.

Step 1: Start Step 2: Initialize number of factors of num, f = 0 Step 3. Initialize i = 1 Step 4. Repeat until i<=num: 4.1: If num % i == 0: 4.2: Increment f by 1 4.3: Increment i by 1 Step 5: If f = 2, then: 5.1: Return True Step 6: Else: 6.1 Return False Step 7. Stop

Algorithm to display a number as sum of two prime numbers:

Step 1: Start Step 2: Read the number from the user, say n Step 3: Initialize loop variable i = 2 Step 4: Initialize flag = false Step 5: Repeat While i <= n/2: 5.1: If CheckPrime(i) == true, then: 5.2: If CheckPrime(n - i) == true, then: 5.2.a: Display i, n-i 5.2.b: flag = true 5.3: Increment i by 1 Step 6: If flag = false, then: 6.1: Display “Number cannot be displayed as sum of two prime numbers” Step 7: Stop

Explanation:

In this problem, we need to check whether a number can be displayed as the sum of two prime numbers. To check this, we need to check whether a number is prime or not, multiple times. Hence, we have written a separate function for doing the prime number check. This function will return true if the number is prime, else returns false.

To do the prime number checking, we must find out the number of factors of the number. We first initialize the number of factors, ‘f’ as 0. Now, we start a loop from 1 to num, where the loop variable is ‘i’. If num% i=0, f is incremented by 1. In this line, we are checking whether the number is divisible by ‘i’ or not. If yes, f is incremented. If the number of factors is equal to 2, the function returns 0, else it returns false.

Now, coming to the main algorithm, we start off by taking the number to be checked as user input and store it in a variable, say ‘n’. We initialize a flag as false and the loop variable I as 2. Now, we check whether i is a prime number. If yes, we check whether ‘n-i’ is a prime number. If both the numbers are prime, we display the numbers and the flag is set as true. Therefore, the number ‘n’ can be displayed as the sum of i and n-i. In the same manner, we check for other pairs. Once the loop is terminated, if the flag is still false, this means the number cannot be displayed as the sum of two prime numbers. Hence, an appropriate message is displayed and the algorithm is terminated.

Note: Here ‘%’ is the modulus operator which returns the remainder value after division.