Untitled

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
1.2 kB
1
Indexable
Never
#include  <bits/stdc++.h>

using namespace std;

int isPrime[1000005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;

    while(true){

        cin >> n;

        if(n==0)
            return 0;

        for(int i=0;i<=n;i++){
            isPrime[i]=1;
        }

        isPrime[0]=0;isPrime[1]=0;
        for(int i=2;i<=sqrt(n);i++){

            if(isPrime[i]==1){

                for(int j=i*i;j<=n;j+=i){
                    isPrime[j] = 0;
                }
            }

        }

        isPrime[2] = 0;

        vector<int> Primes;

        for (int i=3; i<=n; i++)
        {
            if (isPrime[i] == true)
            {
                Primes.push_back(i);
            }
        }


        int flag = 0;

        for (int i=0 ; i<Primes.size(); i++){

        int m = n - Primes[i];

        if (binary_search(Primes.begin(), Primes.end(), m))
        {
            cout << Primes[i] << " + " << m << " = " << n << endl;
            flag = 1;
            break;
        }
        }

        if(!flag)
            cout << "Goldbach's conjecture is wrong." << endl;

    }

}