java - 小于 1 的不同分数的数量

Question

给定一个数字 N ，它被要求找到不同分数的数量，如果减少的分数是 P/Q(P 和 Q 是互质的)，那么 P 和 Q 必须是 <=N . 所以首先我想到了这种天真的方法。

public static void main (String[] args) throws java.lang.Exception
  {
    // your code goes here
    Scanner sc = new Scanner (System.in);
    int t = sc.nextInt();//number of test cases
    while(t-->0){
        int n = sc.nextInt();//integer N
        int count=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                if(gcd(i,j)==1)
                    count++;
            }
        }
        System.out.println(count);
    }
  }
  public static int gcd(int a,int b){
      if(b!=0)
          return gcd(b,a%b);
      else
          return a;
  }

被拒绝为 TLE。然后我想到预先计算提到的值 N<=1000000 .所以我尝试了这个:

public static void main (String[] args) throws java.lang.Exception
  {
    // your code goes here
    Scanner sc = new Scanner (System.in);
    int[] arr = new int[1000001];
    arr[0]=0;
    for(int i=1;i<1000001;i++)
    {
        arr[i]=arr[i-1];
        for(int j=i-1;j>=0;j--)
        {
            if(gcd(i,j)==1)
                arr[i]++;
        }
    }
    int t = sc.nextInt();
    while(t-->0){
        int n = sc.nextInt();
        System.out.println(arr[n]);
    }
  }
  public static int gcd(int a,int b){
      if(b!=0)
          return gcd(b,a%b);
      else
          return a;
  }

但现在它甚至为 N=1 显示 TLE , 2和 3也。即使循环看起来正确，我也无法理解出了什么问题。也欢迎任何更好的方法。
注意:TLE 已超过时间限制

Answer 1

for 循环很好。我很确定 while 循环中出现了问题，即您的条件总是评估为真。它可能与 -> 含义有关，而不是 (t--)>，我相信这就是您想要的。

更好的方法是实现类似 Farey Sequence 的东西或 Stern-Brocot Sequence .