Prime Factorization in o(sqrt(n))

//Prime Factorization in O(sqrt(n))

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		HashMap<Integer,Integer> ob=new HashMap<Integer,Integer>();
		while(n%2==0){
		    if(!ob.containsKey(2))
		    {
		        ob.put(2,1);
		    }
		    else{
		        ob.put(2,ob.get(2)+1);
		    }
		    n/=2;
		}
		for(int i=3;i<=Math.sqrt(n);i+=2)
		{
		    while(n%i==0)
		    {
		         if(!ob.containsKey(i))
		        {
		        ob.put(i,1);
		        }
		        else{
		            ob.put(i,ob.get(i)+1);
		        }
		         n/=i;
		    }
		    
		}
		if(n>2)ob.put(n,1);
		for(Map.Entry<Integer,Integer> x:ob.entrySet())
		{
		    System.out.println(x.getKey()+" : "+x.getValue());
		}
	}
}