主要因素輸出 - 問題是什麼？

-1

我正在進入UVA online programming competition，並正在研究UVA 583（Prime因子）的解決方案。主要因素輸出 - 問題是什麼？

我最近爲此接受了一個Java解決方案。當我嘗試將它翻譯成C++時，即使對於每個測試用例我都會得到WA（「錯誤答案」），但兩個程序都輸出相同的答案。

任何人都可以指出什麼是錯的？

#include <iostream> 
#include <string> 
#include <cmath> 
#include <stdio.h> 
using namespace std; 
int primes [4792]; 
void factorize(int x1){ 
    int c = 0; 
    for(int i = 0;i<4792;i++){ 
     int x2 = primes[i]; 
     while(x1%x2==0){ 
      if(c!=0) 
       cout<<" x "; 
      cout<<x2; 
      c++; 
      x1/=x2; 
     } 
    } 
    if(x1>1 && c!=0){ 
     cout<<" x "<<x1; 
    } 
    if(c==0) 
     cout<<x1; 
    cout<<endl; 
} 
int main(){ 
    primes[0]=2; 
    primes[1]=3; 
    int count = 2; 
    for(int i=5; i<46340;i+=2){ 
     if(i%6 != 1 && i%6 != 5) 
      continue; 
     int limit = (int)sqrt((double)i); 
     bool isPrime = true; 
     for(int j=0;j<count;j++){ 
      if(primes[j]<limit){ 
       if(i%primes[j]==0){ 
        isPrime = false; 
        break; 
       } 
      } 
     } 
     if(isPrime){ 
      primes[count]=i; 
      count++; 
     } 
    } 
    int x = 0; 
    cin>>x; 
    while(x!=0){ 
     string out; 
     cout<<x<<" = " ; 
     int x1 = x; 
     if(x<0){ 
      cout<< "-1 x "; 
      x1*=-1; 
     } 
     factorize(x1); 
     cin>>x; 
    } 
    return 0; 
}

來源

2012-08-05 segfaulter09

間46個平方等什麼WA和UVA是什麼意思？ – walrii 2012-08-05 15:52:42

請至少顯示問題規範的鏈接。此外，由於您最近爲此接受了Java解決方案，因此如何將它與您的C++解決方案並行進行區分？至少有人可以執行等同性檢查。 – timrau 2012-08-05 15:54:50

@walrii錯誤的答案。 – sepp2k 2012-08-05 15:55:03

while((double)x1/(double)x2 == (double)(x1/x2)){

這幾乎總是一個壞主意。由於浮點運算的精度有限，最終可能會出現在數學意義上兩者完全等價的情況，但上面的測試會產生錯誤。

來源

2012-08-05 16:49:06

我刪除了雙重鑄造比較，並用模數替換，我仍然得到了錯誤的答案。 – segfaulter09 2012-08-05 17:24:59

在您的factorize(int x1)，剛好在while之上，加上if (x2*x2 > x1) break;。

在main()，if(primes[j]<limit){應使用<=，它應該有它{break;}else條款。用<代替<=我很驚訝它在Java中爲你工作。

正因爲如此，與<那裏，你的代碼不承認前46的素數低於46340 - 這使他們越過數組結束 在那裏他們仍然遙不可及。寫數組的結尾本身就不好。

這是因爲它錯誤地識別素數素數的平方，並有5個和46340.

來源

2012-08-05 19:57:34

在Java中不能有'<'，Java會引發'ArrayIndexOutOfBoundsException'，因爲數組只有素數空間，而不是素數的正方形。 – 2012-08-05 20:13:02

好吧，數組的大小必須調整，否則，現在使用了'％'，這會產生正確的因子分解。 – 2012-08-05 21:59:17

（丹尼爾迴應我的評論，我很快就刪除了，半開玩笑地暗示「因數分析」中的循環被改爲4838以補償）。但是把'<'改成'<='在這裏更容易和合適。 – 2012-08-05 22:04:32

主要因素輸出 - 問題是什麼？

回答

相關問題