найти количество чисел, которые имеют простое число факторов

Question

Проблема состоит в том, чтобы найти число делителей числа

экс

for 10 

ANS = 4

так 1,2, 5,10 являются числами, которые являются делителями

т.е. они являются факторами

Constrain ts are num < = 10^6

Я внедрил код для того же, но получил TLE !!

вот мой код

int isprime[MAX]; 

void seive() 
{ 

    int i, 
    j; 

    isprime[0] = isprime[1] = 1; 

    for (i = 4; i < MAX; i += 2) 
     isprime[i] = 1; 

    for (i = 3; i * i < MAX; i += 2) { 
     if (!isprime[i]) { 
      for (j = i * i; j < MAX; j += 2 * i) 
       isprime[j] = 1; 

     } 

    } 

} 
int main() 
{ 

    seive(); 

    int t; 

    long long num; 

    scanf("%d", & t); 

    while (t--) { 

     scanf("%lld", & num); 



      cnt = 0; 

      for (j = 1; j * j <= num; j++) { 
       if (num % j == 0) { 
        cnt++; 

        if (num/j != j) 
         cnt++; 

       } 





     printf("%lld\n", cnt); 

    } 

    return 0; 

} 

Может кто-нибудь помочь мне, чтобы оптимизировать его?

Я также искал об этом, но не получил никакого успеха.

Так что помогите ребятам.

Answer 1

Вы можете попробовать вычислить это математически (я не уверен, что это будет быстрее/проще). В принципе, учитывая простую факторизацию числа, вы должны иметь возможность вычислять количество делителей без особых проблем.

Если у вас есть вход x распадаются на что-то вроде

x = p1^a1 * p2^a2 * ... pn^an 

Тогда число делителей должно быть

prod(ai + 1) for i in 1 to n 

Я бы тогда посмотреть на поиске наименьшее простое < SQRT (х), разделяя это, пока вы не останетесь с простое.Сито может по-прежнему быть полезным, и я не знаю, какой вход вы получите.

Теперь рассмотрим сказанное выше: количество делителей в произведении степеней простой факторизации (плюс 1). Таким образом, если вы только заботитесь, если результат является простым, тогда вам следует рассматривать только числа, которые являются первичными или степенями простых чисел. И в этом вам тогда нужно только учитывать такие полномочия, что a1 + 1 является простым.

Это должно значительно сократить пространство поиска.

Answer 2

Если простые множители числа, считаются:

x = p1^e1 * p2^e2 * ... * pk^ek 

Тогда число делителей:

(e1 + 1)*(e2 + 1)* ... *(ek + 1) 

Для этого, чтобы быть простым, вам нужно все ei быть 0, за исключением одного , который должен быть простым - 1.

Это справедливо только для простых чисел и степеней простых чисел. Поэтому вам нужно найти, сколько степеней простых чисел находится в [l, r]. Например, 2^6 имеет (6 + 1) = 7 простых факторов.

Теперь вам нужно просто просушить достаточно простых чисел достаточно быстро. Вам нужно всего лишь просеять их в [l, r], поэтому интервал размера max 10^6.

Чтобы просеять непосредственно в этот интервал, удалите кратные 2 непосредственно из [l, r], а также для остальных. Вы можете просеять простые числа до 10^6 и использовать их для последующего просеивания.

Вы можете сделать необходимый подсчет, пока вы также просеиваете.