Tag: Prime Number

Lets write a C program to check whether a user input/entered positive number can be expressed as sum of two prime numbers or not.

Related Read:
C Program To Find Prime Number or Not using While Loop

Prime Number: Any natural number which is greater than 1 and has only two factors i.e., 1 and the number itself is called a prime number.

Note: The user entered number need not be a prime number. But the 2 numbers, sum of which is equal to the original number, must be prime numbers.

For example, if user enters num as 14. Number 14 is not a prime number. We get following result:

3 + 11 = 14
7 + 7 = 14

Numbers 3, 11 and 7 are prime numbers.

Example:

If user enters num = 14;

First Iteration
num = 14;
count = 2; // First prime number in the series

(num-count) => (14-2) = 12;

count + (num-count) = num
2 + 12 = 14.

But 12 is not a prime number. So we discard this 2 + 12 = 14.

Second Iteration
num = 14;
count = 3; // Next Prime Number in the series

(num-count) => (14-3) = 11;

count + (num-count) = num
3 + 11 = 14.

Both 3 and 11 are prime numbers. So we display 3 + 11 = 14.

Third Iteration
num = 14;
count = 5; // Next Prime Number in the series

(num-count) => (14-5) = 9;

count + (num-count) = num
5 + 9 = 14.

But 9 is not a prime number. So we discard this 5 + 9 = 14.

Forth Iteration
num = 14;
count = 7; // Next Prime Number in the series

(num-count) => (14-7) = 7;

count + (num-count) = num
7 + 7 = 14.

Number 7 is a prime numbers. So we display 7 + 7 = 14.

Fifth Iteration
num = 14;
count = 11; // Next Prime Number in the series

(num-count) => (14-11) = 3;

count + (num-count) = num
11 + 3 = 14.

Both 11 and 3 are prime numbers. But we’ve already displayed 3 + 11 = 14 in second iteration. So we do not display it again.

Condition to exit for loop
The condition to exit for loop is: when count is less than or equal to (num – count);

In above case, in fifth iteration: count value is 11. And (num-count) is 3. So 11 <= 3 returns false. So control exits for loop.

Video Tutorial: C Program To Express A Number as Sum of Two Prime Numbers

Source Code: C Program To Express A Number as Sum of Two Prime Numbers

#include<stdio.h>
#include<math.h>

int nxtPrime(int);
int isPrime(int);

int main()
{
    int num, count, flag = 0;

    printf("Enter a positive number\n");
    scanf("%d", &num);

    for(count = 2; count <=(num-count); count = nxtPrime(count))
    {
        if(isPrime(num-count))
        {
            flag = 1;
            printf("%d + %d = %d\n", count, num-count, num);
        }
    }

    if(flag == 0)
    {
        printf("%d cannot be expressed as the sum of 2 prime numbers.\n", num);
    }


    return 0;
}

int nxtPrime(int num)
{
    do
    {
        num++;
    }while(!isPrime(num));

    return(num);
}

int isPrime(int num)
{
    int count, inum, prime = 1;

    inum = sqrt(num);

    for(count = 2; count <= inum; count++)
    {
        if(num % count == 0)
        {
            prime = 0;
            break;
        }
    }

    return(prime);
}

Output 1:
Enter a positive number
14
3 + 11 = 14
7 + 7 = 14

Output 2:
Enter a positive number
5
2 + 3 = 5

Output 3:
Enter a positive number
24
5 + 19 = 24
7 + 17 = 24
11 + 13 = 24

Output 4:
Enter a positive number
34
3 + 31 = 34
5 + 29 = 34
11 + 23 = 34
17 + 17 = 34

Output 5:
Enter a positive number
41
41 cannot be expressed as the sum of 2 prime numbers.

Note: Function nxtPrime() and isPrime() returns integer type data so its return type is int. And both these methods / functions accepts 1 integer type argument.

Logic To Express A Number as Sum of Two Prime Numbers

1. We ask the user to enter a positive number and store it inside variable num. Now we write the for loop. We initialize the loop counter variable count to 2 – because 2 is the first number in prime number series. We iterate through the for loop until count is less than or equal to (num-count). For each iteration of for loop we change the value of count to next prime number in the prime number series.

We use following simple expression to find and printout the result:
count + (num – count) = num;

We already know that value of count is prime number. Next inside for loop we check the second part of above expression i.e., (num-count) for prime number or not. If both count and (num-count) are prime numbers, then we output the values, if not, then we change the value of count to next prime number and check if (num-count) is prime or not. We continue doing this until count is less than or equal to (num-count);

2. We need to get next prime number for loop count variable count. So we need to define (write logic for) nxtPrime() method.

int nxtPrime(int num)
{
    do
    {
        num++;
    }while(!isPrime(num));

    return(num);
}

value of count is passed to nxtPrime() method, which is copied to local variable num. First we increment the value of num inside do block and then check the condition in while. If the number is prime then we exit the do-while loop and return the number orelse we keep incrementing the value of num and check if the new number is prime or not, by passing it to the function isPrime().

Table of all prime numbers up to 1,000:

3. Next we write the logic to check if the number is prime or not. We’ve already explained the complete logic in a separate video tutorial present at C Program To Find Prime Number or Not using While Loop.

int isPrime(int num)
{
    int count, inum, prime = 1;

    inum = sqrt(num);

    for(count = 2; count <= inum; count++)
    {
        if(num % count == 0)
        {
            prime = 0;
            break;
        }
    }

    return(prime);
}

This is the beauty of function. We call the function isPrime() 2 times. Once from main() function and once from nxtPrime() function. This avoids repeating our code. We write the code once in our function and call it any number of times in the program. This is called DRY concept in programming i.e., Do Not Repeat Yourself.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert