Uva 543 - Goldbach’s Conjecture

Problem Link

Solution in c++

#include<bits/stdc++.h>
#include <math.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;
        }
    }
}

bool isPrime(int n) {
    int i, j;
    if (n == 1)
        return 0;

    if (n == 2)
        return 1;

    if (n % 2 == 0)
        return 0;

    int l = sqrt(n);

    for (i = 3; i <= l; i += 2) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

int main() {

    int num;

    while (cin >> num && num) {

        int a = 0, b = 0, m;
        for (int i = num - 1; i >= num / 2; i--) {
            if (isPrime(i)) {

                m = num - i;
                if (isPrime(m)) {
                    if (i % 2 == 1 && m % 2 == 1) {
                        a = i;
                        b = m;
                        break;
                    }
                }
            }
        }

        if (a > 0 && b > 0 && a <= b)
            printf("%d = %d + %d\n", num, a, b);
        else if (a > 0 && b > 0 && b < a)
            printf("%d = %d + %d\n", num, b, a);
        else
            printf("Goldbach's conjecture is wrong.\n");
    }

    return Accepted;
}