A20250603_Amazon_Hackon

/*
A20250603_Amazon_Hackon
#math

you are taking a loan for m amount ,which you need to pay the intrest
but the thing is
you can take them as portions
so for each portions you will have seperate interest
the desired amount for you is >=2 and also you cannot have a portion which is <2
now lets say you have divided them into portions
for the current portion p you can pay (p/k) interest
where k is smallest factor of p which is other than 1
summing the interest of all these portions will give you the final interest i
you need to try to minimise this i

-----------------------------------------------------------------------------------------------------

important thing to be noted here is -


lets say you are taking loan of
7
this can be divided into various ways
like
2 2 3
4 3
2 5
7
their interests would be
1 1 1
2 1
1 1
1

if you observe one thing ,interests of prime portions are always 1
because the lowest factor other than 1 is always the number itself for a prime
so you try to make your required amount as sum of primes may be like below
2 2 3
2 5
7
now out of all these prime sums we need to know which is the best way ,that requires less number of possible primes
may be you can think greedily like attacking the number and shrinking to smallest possible number

but that may not gaurantee you it is the best way  [D] [R] [v]

now to solve this we need goldbach's conjecture theorem
he says
for even's (other than 2) can be represented as just sum of 2 primes [BOOOOM] //strong conjecture (still unproven)
say 42 this will be broken down as 23 and 19
like that it is applied for every even number

for odd numbers it can be either shown as sum of 1 prime num,2 prime nums,3 prime nums at max
hmm
1 prime is the odd num is prime itself
2 prime is (curr odd) = odd + even //even + even can never be odd number and odd + odd can never be odd
now how do we will know which odd + even is the sum that makes curr odd
hmm note that we have constraint that the portions should be prime
that means the even prime is only 2 then you just need to check wether curr odd-2 is prime or not
if the above conditions got failed ,inevitably the answer is 3 ;)




-----------------------------------------------------------------------------------------------------

input -
8


output -
2

*/

import java.util.*;





@SuppressWarnings({"unused","unchecked"})
public class A20250603_Amazon_Hackon{

    static Scanner sc = new Scanner(System.in);

    private static int[] getArray() {
        String[] sArr = sc.nextLine().split(" ");
        int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
        return arr;
    }

    private static char[] getCharArray() {
        String[] sArr = sc.nextLine().split(" ");
        char[] cArr = new char[sArr.length];
        for (int i = 0; i < sArr.length; i++) {
            cArr[i] = sArr[i].charAt(0); // Take the first character of each string
        }
        return cArr;
    }

    private static int getMax(int[] arr) {
        int currMax = Integer.MIN_VALUE;
        for (int curr : arr) {
            currMax = Math.max(currMax, curr);
        }
        return currMax;
    }
    public static boolean isPrime(int curr){
        for(int i = 2;i*i<=curr;i+=1){
            if(curr%i==0){
                // System.out.println("i is "+i);
                return false;
            }
        }
        return true;
    }

    public static void main(String args[]) {
        // prepare the inputs


       int loanAmount = getArray()[0];
       int ans = -1;
       if(loanAmount % 2 == 0){//even ,strong conjecture
         if(loanAmount == 2){
            ans = 1;
         }else{
            ans = 2;
         }
       }else{
         if(isPrime(loanAmount)){
            ans = 1;
         }else if(isPrime(loanAmount-2)){
            ans = 2;
         }else{
            ans = 3;
         }
       }
       System.out.println("ans is "+ans);

    }
}

class Pair{
    int row;
    int col;
    public Pair(int i,int j){
        this.row = i;
        this.col = j;

    }
}