素數分解函數輸出

-1

我做了這個函數，它計算從用戶獲得的數字（n）的素數分解。由於它不會多次打印相同的因子，因此我遇到了問題。素數分解函數輸出

例如：

3960的質因子分解爲：

11 5 3 3 2 2 2

但是我的程序只打印出：

11 5 3 2

誰能幫我查明原因，並幫助我找到解決方案？

void primefact(int n) 
{ 
    Stack f; 
    assert(n >= 0); 
    bool prime; 

    for(int d = 2; d <= n; d++) // Test for factors > 1 
    { 
     if(n % d == 0) 
     { 
      prime = true; 
      for(int j = 2; j < d; j++) // Test for prime 
      { 
       if(d % j == 0) // It is not prime 
       prime = false; 
      } 
      if(prime) 
       f.push(d); 
     } 
    } 

    while(!f.empty()) 
    { 
     cout << f.top() << endl; 
     f.pop(); 
    } 
}

來源

2014-10-29 NinjaZ

這將是一個恆星* *時間，通過這段代碼與調試器行走。 – WhozCraig 2014-10-29 19:52:54

-1

最簡單的代碼： -

for (int i = 2; i <= num; ++i) 
{ 
    while (num % i == 0) 
    { 
     num /= i; 
     std::cout << i << std::endl; 
    } 
}

來源

2014-10-29 19:52:29 ravi

這是分解問題的一個很好的解決方案，但並沒有直接解決OP爲什麼給出的代碼不起作用的問題。 – Caleb 2014-10-29 20:21:09

@NinjaZ：當然會的。只要做'f.push'而不是'cout <<' – 2014-10-29 23:05:41

只要分割輸入，你必須遍歷相同的素數。對於因式分解

來源

2014-10-29 19:51:59

誰能幫我找出原因？

您正在檢查n是否可以被d整除，但隨後您將轉到下一個值。如果n可被d和d整除，則需要實際將n除以d並再次檢查d。

我們以12爲例。主要因素是[3, 2, 2]。您的代碼做到這一點：

n = 12, d = 2 
n % d == 0? Yes. Push d. d = d + 1 
n % d == 0? Yes. Push d. d = d + 1 
n % d == 0? No. d = d + 1 
n % d == 0? No. d = d + 1 
n % d == 0? No. d = d + 1 
n % d == 0? No. d = d + 1 
// and so on until d == n

你想要的代碼，這是否：

n = 12, d = 2 
n % d == 0? Yes. Push d. n = n/d  // n is 6, d is 2 
n % d == 0? Yes. Push d. n = n/d  // n is 3, d is 2 
n % d == 0? No. d = d + 1    // n is 3, d is 3 
n % d == 0? Yes. Push d. n = n/d  // n is 1 so you're done

來源

2014-10-29 19:54:27 Caleb

所以，問題的原因是你只是檢查每個數字來看*如果它是一個主要因素，對吧？但是，每當你找到一個主要因素時，你想用這個因子除以n，然後再次嘗試相同的因子。在爲您編寫代碼的過程中，我不確定如何更好地解釋問題。 – Caleb 2014-10-29 21:02:59

你可能知道自己，你的算法是遠遠沒有達到最佳。所以這不會對性能造成太大的影響。更換

if(prime) 
    f.push(d);

與

if (prime) 
{ 
    for (int d1 = d; n % d1 == 0; d1 *= d) 
     f.push(d); 
}

來源

2014-10-29 23:09:53

素數分解函數輸出

回答

相關問題