как уменьшить временную сложность для получения фактора длинного типа

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

Попробуйте