Uva 10311 - Goldbach and Euler

Problem Link


Solution in c++

#include<bits/stdc++.h>

using namespace std;

/// Typedef
typedef long long ll;

#define sc1(a) scanf("%lld",&a)
#define sc2(a, b) scanf("%lld %lld",&a,&b)

#define pf1(a) printf("%lld\n", a)
#define pf2(a, b) printf("%lld %lld\n",a,b)

#define mx 1000000
#define mod 1000000007
#define PI acos(-1.0)
#define Accepted 0

#define size1 100000005

int drx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dcy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

int dirx[4] = {-1, 0, 1, 0};
int diry[4] = {0, -1, 0, 1};


ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


bool check[size1];
int twinPrime[size1];
vector<ll> prime;

void seive() {
    memset(check, true, sizeof(check));

    for (ll i = 4; i < size1; i += 2) check[i] = false;

    check[0] = check[1] = false;

    for (ll i = 3; i * i < size1; i += 2) {
        if (check[i]) {
            for (ll j = i * i; j < size1; j += (2 * i))
                check[j] = false;
        }
    }
    //for (int i = 2; i < size1; i++) if (!check[i]) prime.push_back(i);
}

ll sumOfDigits(ll num) {
    ll ans = 0;

    while (num != 0) {
        ans += num % 10;
        num /= 10;
    }

    return ans;
}

ll save[size1];

void cumulativeSum() {
    save[0] = save[1] = 0;

    for (ll i = 2; i <= size1; i++) {

        ll sum = 0;
        if (check[i])
            sum = sumOfDigits(i);

        if (check[sum]) save[i] = save[i - 1] + 1;
        else save[i] = save[i - 1];
    }
}

void allTwinPrime() {
    int index = 1;
    for (int i = 0; i < size1; i++) {
        if (check[i] && check[i + 2]) {
            twinPrime[index++] = i;
        }
    }
}

int main() {

    seive();

    ll num;

    while (cin >> num && num) {

        cout << num << " ";

        if (num & 1) {

            if (check[num - 2]) {
                cout << "is the sum of 2 and " << num - 2 << "." << endl;
            } else {
                cout << "is not the sum of two primes!" << endl;
            }
            continue;
        }

        bool checkPrime = false;
        for (ll i = num / 2 - 1; i >= 0; i--) {
            if (check[i] && check[num - i]) {
                cout << "is the sum of " << i << " and " << num - i << "." << endl;
                checkPrime = true;
                break;
            }
        }

        if (checkPrime == false)
            cout << "is not the sum of two primes!" << endl;
    }

    return Accepted;
}