I am getting correct output for all inputs with in the constraints !
I don`t understand why am i getiing WA?
Kindly please help me out !
I have used sieve for prime factorisation with precomputation (upto 10^6)
and store all the unique prime factors of given input in arraylist
and computed the phi using the n*(1-1/p) formula.
Code:-1:
import java.io.;
import java.util.;
import java.lang.;
class Sieve {
ArrayList memo = new ArrayList();
int n=1000000;
void prime(int k){
loop:{
int bool[]=new int[n+1];
for(int z=0;z<=n;z++)
bool[z] = 0;
for (int i = 2; ii<= n; i++) {
if(bool[i]==0){
bool[i]=i;
for (int j = i*i; j<= n; j=j+i) {
if(bool[j]==0){
bool[j]=i;
}
}
}
}
int r=1;
if(k==1){
System.out.println(1);
break loop;
}
float result=k;int s=0;
while(k>=2){
//System.out.print(bool[k]+" ");
if (memo.contains(bool[k])) {
//System.out.printf("grabbing memo[%d]\n", n);
//return memo.get(n);
//System.out.println("inside if ");
}
else {
// System.out.println("inside else");
memo.add(bool[k]);
++s;
}
k=k/bool[k];
// System.out.println(k);
}
//System.out.println(result);
/*
for (int k = 2; k <=n; k++) {
if(bool[k] == true)
System.out.print(k + " ");
}*/
for (int i=0; i<memo.size(); i++)
{
result*=(1.0 - (1.0 / (float)memo.get(i)));
}
System.out.println((int)result);}
}
public static void main(String[] args) throws java.lang.Exception{
try{
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T-->0){
int k=sc.nextInt();
Sieve s=new Sieve();
s.prime(k);
}
}
catch(Exception e){}
}
}
