Coprime Conundrum

  • + 0 comments

    I know the competition has been over. But I still trying to get rid of timeouts. Can any one help me here to get rid of timeouts.I have 10 test cases passed and 10 test cases time out. Here is my code.

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

    public class Solution { public static boolean areCoPrime(int a, int b){ if (GCD(a,b)==1) return true; return false; } public static int GCD(int a, int b) { if (b==0) return a; return GCD(b,a%b); }

    public static void main(String[] args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int sum = 0; for(int k=1;k<=n;k++){
    for(int p=2;p*p if(k%p==0) {
    int q = k/p;
    if (areCoPrime(p,q)) sum++; } } } System.out.println(sum); } }