查找整數的因數

我需要找到codechef中問題的整數（n）的除數的數目。我寫了下面的程序來計算除數的數量。但該計劃超出了時間限制。有沒有什麼辦法來優化我的方法來解決這個問題？你能提出一個更快的算法嗎？查找整數的因數

#include<iostream> 
#include<math.h> 
using namespace std; 
int main() 
{ 
int n,i=1,d=0; 
     while(i<=sqrt(n)) 
     { 
      if(n%i==0) 
      { 
      d++; 
      if(i!=(n/i)) 
       d++; 
      } 
      i++; 
     } 
    cout<<d;

來源

2016-02-04 Vinitra

從這裏開始：https://www.google.com/search?num=100&q=number+of+divisors –

當你做INT N，I = 1，d = 0;你的n和i都是1，所以我在while（i <= sqrt（n））永遠不會小於1的平方根。這就是爲什麼它永不停止。 – Atirag

據我所知，你只需要一些除數。找到所有的素數因子並編寫x1^a1 * x2^a2 ... * xn^an。除數等於(a1+1)*(a2+1)*...*(an+1)

例如，12=2^2*3^1，因此，它具有(2+1)*(1+1) = 6除數，即1,2,3,4,6,12。我沒有測試代碼，但它應該工作。

int main() 
{ 
    int n,i=2,d=0; 
    int num_div = 1; 
    while(i <= sqrt(n)) 
    { 
     int cnt = 0; 
     while(n % i == 0){ 
      cnt++; 
      n /= i; 
     }     
     if (cnt != 0) 
      num_div *= (cnt+1); 
     i++; 
    } 
    cout<<num_div; 
}

入住這answer

來源

2016-02-04 18:46:41 smttsp

查找整數的因數

回答

相關問題