4 is not a prime sample test case is wrong....

CAN ANYONE EXPLAIN ME THE CONCEPT BEHIND THIS QUESTION AND WHAT MATHS IS APPLIED HERE.. I READ THE SOLUTIONS BUT DIDNT UNDERSTAND THEM.. everybody in their code have that loop with mask variable and i am not really getting hold of it

CAN ANYONE EXPLAIN ME THE CONCEPT BEHIND THIS QUESTION AND WHAT MATHS IS APPLIED HERE.. I READ THE SOLUTIONS BUT DIDNT UNDERSTAND THEM.. everybody in their code have that loop with mask variable and i am not really getting hold of it

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); } }

Can anyone explain how to implement the code for finding the co-primes of p with range [p+1,R] ? Or how to implement inclusion exclusion principle ?