如何降低获取长型因子的时间复杂度

Question

我必须找到某个特定数字的因子并将其存储在数组列表中，最后我必须根据该参数的索引值检索一个数字。
我得到了小输入的正确结果，但对于大输入（n = 10^15），我无法通过测试用例。

我正在运行我的循环到'N/2'，然后我知道，这是最糟糕的时间复杂度之后，我尝试了 Math.sqrt（n），通过它我无法通过一些测试用例，因为循环很早就完成，因此我错过了一些因素。

public static long pthFactor(long n, long p) {
// Write your code here
ArrayList<Long> al=new ArrayList<>();
for(long i=1;i<=n/2;i++)
{
    if(n%i==0)
    al.add(i);
}
al.add(n);
if(p<=al.size())
{
int index=(int)(p-1);
return al.get(index);
}
else
return 0;
}

按照这个逻辑，我得到了预期的结果，但对于某些测试用例，我得到了超时，所以如何降低这里的时间复杂度。

Answer 1

只需迭代直到math.sqrt(n) .但是，如果i是n的一个因素，那么n/i也是如此。

for(long i=1; i * i <= n; i++)
{
    if(n % i == 0) {
        al.add(i);
        if (i != n/i) {
            al.add(n/i);  // prevent counting twice for square integers
        }
    }
}

Answer 2

for(long i=1;i<=Math.sqrt(n);i++)
{
    if(n%i==0){
    if(n/i==i)
    al.add(i);
    else {
    al.add(i);
    al.add(n/i);
    }
}
}
Collections.sort(al);

试试看