Есть ли способ сократить время выполнения этого кода?

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

int a,count=0; 
cin>>a; 
for(int i=2;i<=a/2;i++) { 
    if(a%i==0) { 
     count=count+i; 
    } 
} 
count++; 
cout<<count;

источник

2015-10-31 Bhavya Bhatia

Вы хотите, чтобы уменьшить временную сложность, или время выполнения? Это разные вещи. TLE обычно означает, что вы хотите сократить время выполнения, а не сложность времени. –

Хорошо, тогда я хочу уменьшить время выполнения ... есть ли какой-нибудь способ? .... и, как я уже упоминал, этот код вычисляет сумму всех делителей номера, который принимается как вход –

Есть ли у вас предположения относительно значение 'a'? возможно, использование нескольких потоков будет полезно здесь. –

Я бы сказал, что идти до SQRT (а). Каждый раз, когда у вас есть остаток 0, добавьте i и a/i. Вам нужно будет позаботиться об угловых случаях, но это должно снизить временную сложность. В зависимости от того, насколько велика a, это должно быть быстрее. Для небольших значений это может быть медленнее.

источник

2015-10-31 18:20:04 Imran

Почему это будет медленнее? –

Так как у вас могут быть дополнительные проверки в случае углового случая, например, это идеальный квадрат, поэтому вы не хотите считать делитель и коэффициент (a = 4 приведет к 2 с вашим существующим кодом и может привести к 4, если у вас нет чек посчитать его один раз.) Эта дополнительная проверка потребует дополнительного времени, но я не думаю, что вы сможете заметить разницу. – Imran

Каковы будут угловые случаи? –

Вы можете запустить петлю на sqrt(a), а не a/2, если бы суммировать два делители времени: count += i + a/i

источник

2015-10-31 18:18:00

Эта проблема может быть оптимизирована с помощью простой факторизации.

Let’s assume any number’s prime factor is = a ^n*b^m*c^k 
Then, Total number of devisors will be = (n+1)(m+1)(k+1) 
And sum of divisors = (a^(n+1) -1)/(a-1) * (b^(m+1)-1)/(b-1) *(c^(k+1)-1)/(c-1) 
X = 10 = 2^1 * 5^1 
Total number of devisors = (1+1)(1+1) =2*2= 4 
Sum of divisors = (2^2 – 1) /1 * (5^2 -1)/4 = 3 * 24/4 = 18 
1+2+5+10 = 18

источник

2015-10-31 18:38:02 Sumeet

Спасибо всем за help..I получил ответ

 bool is_perfect_square(int n) 
    { 
    if (n < 0) 
    return false; 
    int root(round(sqrt(n))); 
    return n == root * root; 
    } 
    main() 
    { 
    int t; 
    cin>>t; 
    while(t--) 
    { 
    int a,count=0; 
    cin>>a; 
    bool c=is_perfect_square(a); 


    for(int i=2;i<=sqrt(a);i++) 
    { 
     if(a%i==0) 
     { 
      count=count+i+a/i; 

     } 

    } 
    if(c==true) 
    { 
       count = count - sqrt(a); 
    } 
    count++; 
    cout<<count<<endl; 
    } 


}

источник

2015-10-31 19:58:14

Есть ли способ сократить время выполнения этого кода?

ответ

Смежные вопросы