Codeforces Round #382 (Div. 2) (D. Taxes)

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers.

The conjecture has been shown to hold for all integers less than 4 × 10¹⁸

Bismillahir Rahmanir Rahim

///Author: Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

bool prime(ll num)

{

    for(ll i=2;i*i<=num;i++)

        if(num%i==0) return false;

    return true;

}

int main()

{

    ll num;

    cin>>num;

    if(prime(num)==true) cout<<"1"<<endl;

    else if(num%2==1)

    {

        if(prime(num-2)==false) cout<<"3"<<endl;

        else cout<<"2"<<endl;

    }

    else cout<<"2"<<endl;

    return 0;

}

///Alhamdulillah

Problem Link: https://codeforces.com/problemset/problem/735/D