DownToZero.java

package com;

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class DownToZero {
    static int counter =0;
    static int MAX = 1000000;
    static boolean[] prime = new boolean[MAX+1];
    
    static{
    
        for (int p=2; p*p<=MAX; p++)
        {
            // If prime[p] is not changed, then it is a prime
            if (!prime[p])
            {
                // Update all multiples of p
                for (int i=p*2; i<MAX; i += p)
                    prime[i] = true;
            }
        }
    }   
   
    
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int Q =  scan.nextInt();
        for(int i=0;i<Q;i++){
            printMoves(scan.nextInt());
            System.out.println(counter);
            counter = 0;
        }
    }
    
    static void printMoves(int number){
    	  if(number==0)
              return;
            
          if(!prime[number]){
              number--;
              }
          else{
              int factorNumber =2;
               while(factorNumber < number){
                  if(number % factorNumber == 0){
                      number = number/factorNumber;
                      number = Math.max(number,factorNumber);
                      break;
                  }
                  
                   factorNumber ++;
              } 
          }
      counter++;
      printMoves(number);
      return;  
    }
}