篩選後找到主要因素的最快方法

我已將所有質數存儲在sieve之後的矢量primes範圍內。現在我想在短時間內找到n的所有主要因素。篩選後找到主要因素的最快方法

我的代碼：

i=0 
    while(primes[i]<=n) 
    { 
     if(n%primes[i]==0) 
     { 
      cout<<primes[i]<<endl; 
     } 
     while(n%primes[i]==0) 
      n/=primes[i]; 
     i++; 
    }

但是，這是沒有效率的，請提出任何修改可能。謝謝！

來源

2015-10-05 cold_coder

我認爲這應該更有效，因爲我消除了代碼中的其他循環。我在C＃中測試了這個，除了我用硬編碼測試了它。

我認爲這是你想看的代碼。希望它更有效率。我寫在C＃中，並沒有質數列表，這樣我就硬編碼（或夠了我的例子）

代碼我想將工作基於把你的代碼

i = 0 
while(n > 1) 
{ 
    if(n % primes[i] == 0) 
    { 
     cout<<primes[i]<<endl; 
     n /= primes[i]; 
    } 
    else 
     i++; 
}

代碼我在C＃中寫道，我認爲模仿你的代碼或者至少我認爲你在做什麼。

 int n = 1806046; 
     int[] primes; 
     primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 439, 601, 733, 941, 1151 }; 
     int i = 0; 
     while (n > 1) 
     { 
      if (n % primes[i] == 0) 
      { 
       comboBox1.Items.Add(primes[i]); 
       n /= primes[i]; 
      } 
      else 
       i++; 
     }

這是我測試的代碼，並以C＃爲基礎。哪些工作很好，迭代所有數字，而不是隻有素數。

 int x = 1806046; 
     int i = 2; 

     while (x > 1) 
     { 
      if (x % i++ == 0) 
      { 
       x /= --i; 
      } 
     }

來源

2015-10-05 18:47:55 Timmy

實際上它是採取幾乎相同的時間。 –

哦，夥計，這需要多快？你也在C編碼？ – Timmy

我使用C++，在一個文件中有10^7左右的數字，數字的約束是從1 <= n <= 10^6。約1.5秒內（不考慮打印時間） –

您正在檢查所有質數高達n。你不需要那樣做。一旦刪除了包括sqrt(n)在內的所有因素，那麼剩餘的不合格部分本身就是素數或者是1。

由於沒有更多的素數因子可以找到，因此可以在n == 1時退出外部循環。想象一個像16這樣的數字，有很多小素數因素。

您每次都通過外循環進入內循環。你不需要那樣做;當您的if爲真時，您只需要內循環。

一旦進入if，您可以通過將while循環更改爲do循環來節省重複模數計算。

i = 0; 

// Find prime factors up to square root. 
limit = sqrt(n); 
while ((primes[i] <= limit) && (n > 1)) 
{ 
    if (n % primes[i] == 0) 
    { 
     cout << primes[i] << endl; 
     do 
     { 
      n /= primes[i]; 
     } while (n % primes[i] == 0); 
    } 
    i++; 
} 

// Find possible factor above square root. 
if (n > 1) 
{ 
    cout << n << endl; 
}

我還沒有測試代碼，所以更好地測試它自己。

來源

2015-10-06 16:35:02 rossum

IMO這是一個快速循環結構。一個很大的改進是在這段時間後重新計算'limit'，但仍然在if語句中。 'n'（無構成部分）已經減少了，所以我們不必看得太遠。 – DanaJ

我認爲。這真的取決於平方根計算的速度。可能最好嘗試兩種方法，並查看給定機器上哪個更快。我也有一個印象，cold_coder想要一個相當簡單的答案，所以我決定不包括那個調整。因人而異。 – rossum

解決這個問題的關鍵是理解只能有一個素數> = square_root（N）。

所以，你可以迭代通過素數列表square_root（N）。你可以這樣做下面這段代碼：

Factor generation

來源

2015-10-27 19:08:58 Honour

篩選後找到主要因素的最快方法

回答

相關問題