java - 求偶数约数总数的有效方法

Question

我必须找到给定数字的偶数除数的数量。为此，我尝试了。我得到了正确的输出，但时间复杂度超过了要求。
问题:- 第一行包含测试用例 T 的数量，后跟 T 行，每行包含一个整数 N
输出应该是 - 对于每个测试用例，在一行中打印所需的答案。
我如何降低给定代码的复杂性。或者任何人都可以建议更有效的方法...

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class TestClass {
    public static void main(String args[]) throws Exception {
        // Read input from stdin and provide input before running
        String frt = "";
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();    
        int T = Integer.parseInt(line);     
        int[] inp = new int[T];
        for (int i = 0; i < T; i++) {           
            int x = Integer.parseInt(br.readLine());
            inp[i] = x;

        }
        int[] ans = new int[T];
        int count = 1;
        for (int i = 0; i < T; i++) {
            int x = inp[i];
            if (x % 2 == 0) {
                for (int j = 2; j <= x / 2; j = j + 2) {
                    if (x % j == 0)
                        count++;
                }
            } else
                count = 0;
            ans[i] = count;
        }
        for (int i = 0; i < T; i++)
            System.out.println(ans[i]);
    }

}

Answer 1

 import java.io.*;

 class Ideone
 {
    public static void main (String[] args) throws Exception
    {

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(br.readLine());
      int i,j,k,n;

      int[] inp = new int[T];
      for (i = 0; i < T; i++) {
      inp[i] = Integer.parseInt(br.readLine());
      }

     //Find all the primes numbers till the square-root of 10^9.
     int MAX, root, arrLen;
     MAX=1000000000;
     arrLen=(int)Math.sqrt(MAX);  // arrLen=31622 
     boolean[] primes=new boolean[arrLen+2]; // No need to find all the primes numbers till MAX

     primes[0]=primes[1]=false;
     for(i=2;i<arrLen;i++)
           primes[i]=true;


     // Using Sieve of Eratosthenes
    // Square root of 31622 is 177.8
    root=(int)Math.sqrt(arrLen); // root=177
    for(i=2;i<=root;i++)
    {
       if(primes[i])
       {
           n=i*i;
           k=0;

           //arrLen is the length of primes array.
           for(j=n; j<arrLen; k+=1, j=n+(i*k))
                  primes[j]=false;
       }
   }

    int[] ans = new int[T];
    for( i = 0; i < T; i++) {
         n = inp[i];

         if(n%2==1)
         {
             ans[i]=0; // Odd numbers will have 0 even divisors
         }
         else
         {

          int[] facts=new int[50];
          for(k=0;k<50;k++)
              facts[k]=1;

        facts[0]=0; // fact[0] will contain the highest power of 2 that divides n.
        while(n%2==0)
        {
             facts[0]+=1;
             n=n/2;
        }           

        // Prime factorizing n
        j=1;
        for( k=3; k<arrLen; k+=2)
        {
            if(primes[k] && n%k==0)
            {
                while(n%k==0)
               {
                    facts[j]+=1;
                    n=n/k;
               }
               j+=1;
            }
            if(n==1)  // To check if n has been completely divided or not.
               break;
       }

       if(n!=1) // To check if there is any prime factor greater than the square root of MAX.
       {
            facts[j]+=1;
            j+=1;
       }

       int count=1;
       for(k=0;k<j;k++)
            count=count*facts[k];

        ans[i]=count;
       }
}

   for ( i = 0; i < T; i++)
           System.out.println(ans[i]);

     }
 }

我觉得这个问题可能已经发布在任何竞争性的编码平台上，比如 HackerEarth。如果是这样，那么请不要在 StackOverFlow 上发布直接问题(在我看来)。无论如何，我已经测试了我的代码并且它运行正确。在无法降低时间复杂度的问题中，首先确保不会创建不必要的对象。在内存中创建对象是一个耗时的操作。避免不相关的对象和变量的创建。上面的代码仍然可以优化，但这会降低其可读性。 :)

此外，在解决问题之前，请尝试找出各种测试用例。就像奇数有 0 个偶数因子一样。所以通过检查一个数是否为奇数，可以减少一些运算。

对上面的代码进行更多解释:一个数的约数为: (N1+1)(N2+1)(N3+1)... 其中 N1、N2、N3 等是该数的质数倍数的幂。现在如果 N1 代表 2(唯一的偶素数)，那么该数的偶数约数为:N1*(N2+1)*(N3+1)...

在facts[]数组中，facts[0]对应N1，而N2、N3等则存储在facts[1]、facts[2]等中。facts[0] 初始化为 0，其他初始化为 1。计数存储最终的乘积:N1*(N2+1)*(N3+1)...，它等于原始数字的偶数约数的数量。