Как получить общее число не премьер факторов с быстрым временем выполнения?

Question

Я изучаю C на конкурентном сайте программирования.Вопрос, учитывая число, сколько не основных факторов число имеет?Я могу сделать это с помощью своего кода следующим образом:

#include <stdio.h>

int totalNPF(int n){
    int totalFactor = 1, temp = 0, primeFactor = 0;
    for(int i=2; n!=1;){
        while(n % i == 0){
            n /= i;
            temp++;
        }
        if(temp != 0){
            totalFactor *= (temp+1);
            primeFactor ++;
        }

        i++;
        temp = 0;
    }

    return totalFactor-primeFactor;
}

int main(){
    int T, n;
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        scanf("%d", &n);
        printf("%d\n", totalNPF(n));
    }

    return 0;
}

Я использую концепцию теории чисел, но она все еще медленная.Время выполнения выше 1 с.Кто-нибудь знает, как улучшить скорость, чтобы я мог получить скорость около 1 с или ниже?

ПРИМЕЧАНИЕ. Число ограничено 2x10 ^ 6

Answer 1

Программу можно сделать быстрее, изменив for(int i=2; n!=1;){ на for(int i=2; i*i <= n;){.Это прекращает поиск факторов, когда n меньше квадрата текущего фактора-кандидата.После этой точки не может быть никаких простых факторов, кроме самого n, поскольку, если бы j был основным фактором больше i, то n/j был бы фактором меньше i.Но такой фактор был бы извлечен из n ранее в цикле.

Поскольку это означает, что цикл может завершиться с n, являющимся основным фактором, необходимо вставить некоторый код после цикла, чтобыпроверить, больше ли n, чем 1, и, если это так, скорректировать totalFactor и primeFactor соответственно.

Программу также можно ускорить, проверяя только простые числа в качестве подходящих факторов вместо проверки каждого целого числаот 2 доОбратите внимание, что поскольку программа должна поддерживать числа до 2 000 000, а новый цикл остановится на квадратном корне из n, необходимы только простые числа до 1414.Список таких простых чисел можно легко подготовить заранее.