CODEWITHSUNDEEP
c
user8630652
user8630652

Reputation:

Program in C to Check Whether a Number can be express as Sum of Two Prime Numbers. I am getting repeated results

I wrote the following code in c-

/* Function to check whether the number is prime or composite*/
int prime(int a)
{
    int i;
    int count=0;
    for(i=1;i<a;i++)
     {
         if (a%i==0)
         {
            count+=1;
         }
    }
    if (a<=1)
    {
        return 0;

    }
    else if (count>1)
     {
    return 1;

    }
    else
    {
        return 2;
    }
}
/* Code for the main function*/
int main()
{
    printf("Enter your desired number");
    int a;
    scanf("%d",&a);
    int i;
     for(i=2;i<a;i++)
    {
        if (prime(i)==2 && prime(a-i)==2)
        {
            printf("The sum of %d and %d is %d\n",i,a-i,a);
        }
    }
    return 0;
}

The problem i am getting is that the result for the number 16 comes as follows: The sum of 3 and 13 is 16 The sum of 5 and 11 is 16 The sum of 11 and 5 is 16 The sum of 13 and 3 is 16 I don't want the cases to be repeated . Please help

Upvotes: 0

Views: 2049

Answers (2)

Nikhil Wagh
Nikhil Wagh

Reputation: 1498

I did the code in c++, if you are not familiar with it, it is quite similar to c only for competitive coding. Your logic is not good you might get a TLE (Time limit exceeded). Instead do this :

  1. Store all your primes before hand you can do this in O(x*sqrt(x)) time,
  2. and then use set to find the whether that number exists in your already created set of primes, you can do that in O(log(n)) time.

If you are having trouble understanding read about it here.

#include<bits/stdc++.h>
using namespace std;
set<int> primes;
int main()
{
    int i,j,x;
    cout<<"Enter your number: ";
    cin>>x;
    //Store all the primes before hand
    for(i = 2; i<x; i++)
    {
        int square_root = sqrt(i);
        for(j=2;j<=square_root;j++)
        {
            if(i%j==0)
                break;
        }
        if(j > square_root) // j == (square_root + 1) i.e the loop never broke or it never found a number which could divide it hence i is a prime.
        {
            primes.insert(i);
        }
    }

    //Now find whether it comprises of two primes or not
    for (i=2; i<=x/2 ;i++)
    {
        if(primes.find(i) != primes.end() && primes.find(x-i) != primes.end()) 
        {
            cout<<"The sum of "<<i<<" and "<<(x-i)<<" is "<<x<<endl;
        }
    }
}

Expected output:

Enter your number: 16
The sum of 3 and 13 is 16
The sum of 5 and 11 is 16

and it also works for 4. :P 

Enter your number: 4
The sum of 2 and 2 is 4

Upvotes: 0

Carey
Carey

Reputation: 670

Stop when you reach halfway. All factors will be symmetric after the halfway point.

#include <stdio.h>

int prime(int a)
{
    int i;
    int count=0;
    for(i=1;i<a;i++)
     {
         if (a%i==0)
         {
            count+=1;
         }
    }
    if (a<=1)
    {
        return 0;

    }
    else if (count>1)
     {
    return 1;

    }
    else
    {
        return 2;
    }
}
int main()
{
    printf("Enter your desired number");
    int a;
    scanf("%d",&a);
    int i;
     for(i=2;i<(a/2);i++)
    {
        if (prime(i)==2 && prime(a-i)==2)
        {
            printf("The sum of %d and %d is %d\n",i,a-i,a);
        }
    }
    return 0;
}

Output:

Enter your desired number16
The sum of 3 and 13 is 16
The sum of 5 and 11 is 16

Upvotes: 1

Related Questions