PRIMEG - EDITORIAL

PROBLEM LINK:

Contest
Practice

Setter: Raj Tiwari
Tester: Nishit Patel

DIFFICULTY

Easy

PROBLEM

Huzaifa and Vedant are childhood friends. It’s Huzaifa’s 18th birthday and Vedant wants to gift him something very special. Vedant knows that Huzaifa is very fond of prime numbers. Vedant has a number N with him. In order to impress Huzaifa, he decides to represent N as the sum of k prime numbers but this will cost him k units (k is the number of prime numbers used whose sum equals N ). However, he can also cheat. He may increase/decrease N by a number m, but this will cost him additional |m| units. Help Vedant prepare his gift for Huzaifa such that the cost is minimum.

EXPLANATION

As per Goldbach’s conjecture, every positive even integer can be written as the sum of two primes.
Thus, all prime numbers can be represented with a cost of 1, while all even numbers (other than 2) can be represented with a cost of 2. The odd numbers can be incremented/ decremented by 1 to make an even number and then be represented as a sum of two primes with a total cost of 3 except in cases when an odd number can be represented by 2 + a prime number, thus with a cost of 2.

TIME COMPLEXITY

The time complexity is O(1).

SOLUTION

Setter's Solution
//Author : Raj Tiwari
#include <bits/stdc++.h>

using namespace std;
int isPrime(int n)
{
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;

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

for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0)
        return 0;

return 1;
}

int main ()
{

    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        if (n%2 == 0)
        {
            cout<<"2\n";
        }
        else if (isPrime(n) == 1){
            cout<<"1\n";
        }
        else if (isPrime(n-2) == 1){
            cout<<"2\n";
        }
        else{
            cout<<"3\n";
        }
    } 
}
Tester's Solution
#include <bits/stdc++.h>

using namespace std;


int prime(int n)
{
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;

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

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;

    return 1;
}

int main ()
{

    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        if (prime(n) == 1){
            cout<<"1"<<endl;
        }
        else if (n%2 == 0)
        {
            cout<<"2"<<endl;
        }
        else if (prime(n-2) == 1){
            cout<<"2"<<endl;
        }
        else{
            cout<<"3"<<endl;
        }
    }
}