hackerrank euler 69 : https://www.hackerrank.com/contests/projecteuler/challenges/euler069

gistfile1.txt

//hackerrank euler 69 : https://www.hackerrank.com/contests/projecteuler/challenges/euler069
 import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class node {
    int max;
    int n;  
    double phiratio;
    public node(int max,int n,double phiratio){
      this.max = max;
      this.n = n;
      this.phiratio = phiratio;
    }
}
public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Map<Integer,node> map = new HashMap<Integer,node>();
        double max = 0;
        int ans = 0;
        int t = in.nextInt();
        for(int i=0; i < t; i++) {
            int total = in.nextInt();
            if( map.containsKey(total) ){                
              node n = map.get(total);
              ans = n.max;
            }          
            else{
            int start = map.size() > 2 ? map.size():2;
              
              for(int j=start ; j <= total ;j++) {
                   int n = j;
                   int temp = 2;
                   int count = n-1;
                   while( temp < n ){
                       if( isPrime(temp) && n%temp == 0 ){
                         //our logic is if temp is prime and is not prime to n 
                           count -= (n/temp)-1;
                       }
                       temp++;
                   }
                   double d= n/(double)count;
                   if( max < d ){
                      ans = n; 
                      max = d;
                   }  
                  node newN = new node(ans, j , d);          
                  map.put( j ,newN );
              } 
            }
            System.out.println(ans);
       }
      
    }
    public static boolean isPrime( int n ){
    int temp = 2;
    while( temp*temp < n ){
      //sqrt of (n) is sufficient to find prime
        if( n%temp == 0 )
            return false;
        temp++;
    }
    return true;
}

}
























//output of n=8 : 1,3,5,7
/*
lets take n = 8. 
temp = 2 , count = 8 
8%2 == 0 , count = 8- (8/2-1) = 5

temp = 3 count = 5
8%3 != 0

temp = 4 count = 5
skip

temp =5 count =4
8%5 !=0

temp = 6 count =5
skip

temp = 7 , skip


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

10    1,3,7,9 
//for 10 
10/2 = 5
so 5-1 =4 are total multiples of 2

for 2 :
so all multiples of 2 that are less than 10 we'll substract from actual count
so count = 10-4 

for 3 :

10%3 != 0
skip

for 4: 
skip since we already take that into account.
*/