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

 

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

Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

bool is_prime(ll n)

{

    if(n!=2&&n%2==0)

        return false;

    for(ll i=3; i*i<=n; i+=2)

    {

        if(n%i==0)

            return false;

    }

    return true;

}

int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    ll  n;

    cin>>n;

    if(is_prime(n))cout<<"1"<<endl;

    else  if(n%2==0)cout<<"2"<<endl;

    else if(is_prime(n-2))cout<<"2"<<endl;

    else

        cout<<"3"<<endl;

}