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。然后我想到了预先计算前面提到的值。所以我试了一下：

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

但现在它甚至在{}、{}和{}也显示出TLE。即使循环看起来是正确的，我也无法理解哪里出了问题。我们也欢迎任何更好的方法
注：TLE为超出时间限制

Answer 1

您可以使用Euler's totient function和动态编程

步骤1：生成最大可能值n的所有素数

步骤2：计算所有1 <= i <= max possible value of n的totient[i]。为此使用动态规划

• totient[1] = 0

• totient[i] = i - 1如果i是素数

• totient[i] = totient[i/d] * totient[d]对于任何除法i的d（循环素数以查找d）

步骤3。具有p < q <= i的不可约分数p/q的数量为totient[2] + totient[3] + totient[4] + ... + totient[i]（Farey sequence长度）。计算总方向时也要计算

• numberOfFractions[1] = 0

• numberOfFractions[i] = numberOfFractions[i-1] + totient[i]

Answer 2

for循环很好。我很确定while循环中出现了一些问题，也就是说，您的条件总是评估为true。这可能与->；意思是暗示而不是（t）>；，我相信这就是你想要的

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