素因子

Question

問題是寫一個數n作爲在C++其首要因素

例如一個產品14 = 2 * 7

24 = 2 * 2 * 2 * 3

5 = 5

我的代碼是：

#include <iostream> 
#include <cmath> 
using namespace std; 
bool prime(int n) 
{ 
    for (int i=2;i<=sqrt(n);i++) 
     { 
      if (n%i==0) return false; 
     } 
    if (prime) return true; 
} 

int main() 
{ 
    int n; 
    int k=0,a[10000]={0}; 
    cin>>n; 
    while (n!=1) 
     { 
      for (int i=2;;) 
       { 
        if (n%i==0 && prime(i)) {n/=i; a[k]=i;k++; } 
        else i++; 
        if (n==1) break; 
       } 
     } 
    cout<<a[0]; 
    int s=1; 
    while (a[s]!=0) 
     { 
      for (s=1;;s++) 
       { 
        if (a[s]==0) break; 
        cout<<"*"<<a[s]; 
       } 
     } 
    return 0; 
} 

但問題是時間限制和compiler_stderr.txt顯示我此消息：

solver.cpp: In function `bool prime(int)': 
solver.cpp:11: warning: the address of `bool prime(int)', will always evaluate as `true' 

當我進入2147483647它再次表明我這個號碼，但後56秒

Answer 1

警告是關於這一行：

if (prime) return true; 

這不叫該函數只是測試函數指針的值。由於它不是空指針，它總是如此。

如果你到達函數中的那個點，那麼除數的測試都沒有成功，所以你應該只返回true而不進行任何測試。

你的程序需要這麼長時間才能返回答案的原因是因爲你正在使用低效的方法來測試素數。您應該只使用Sieve of Eratosthenes來測試其他素數。另外，您應該在循環之前調用sqrt(n)一次，並將其值保存在一個變量中;計算平方根很昂貴，所以你不想每次都這麼做。

Answer 2

我不認爲你應該檢查如果prime定義之前，你的回報是真實的。

試試下面的不是

bool prime(int n) 
{ 
    for (int i=2;i<=sqrt(n);i++) 
    { 
     if (n%i==0) return false; 
    } 
    return true; 
} 

Answer 3

閱讀警告消息。進入你的想法，編譯器有一個原因，並沒有給出這個警告只是爲了好玩。一旦你這樣做，你的錯誤很容易找到：

if (prime) 

prime是一個函數的名稱。在許多情況下，函數的名稱會自動轉換爲函數的地址。在if語句中，檢查控制表達式是否爲零或不爲零。函數prime的地址永遠不是空指針，所以「if」表達式總是會計算爲真。

Answer 4

當前代碼不需要主函數。只要反覆檢查（n％i）== 0就會消除素數的任何冪，因爲它將繼續將i加入到k []中，直到沒有其他因素爲止。假設4是n的一個因子，那麼當我達到4時，它不會是一個因素，因爲當我是2時（k [0] = 2，k [1]），它已經被n/= 2）。 k []將以n的主要因子結束，而不需要主函數。

Answer 5

1. 由於prime地址爲never zero，它總是返回true。所以該程序將完美工作。雖然也許你想以更可讀的方式編寫它：return true;並刪除條件檢查。
2. 2147483647是一個非常大的數字，你的程序運行在O（n^1.5）時間。因此，您可能會認爲它按2147483647^1.5次的順序運行。因此輸出的時間延遲。您可以嘗試使用其他方法（如​​）來降低複雜性。