-1

UVAオンライン プログラミング コンテストに参加し、UVA 583 (Prime Factors) の解決に取り組んでいます。

私は最近、このための 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;
}
4

2 に答える 2

1

のfactorize(int x1)すぐ上whileに、 を追加しif (x2*x2 > x1) break;ます。

では、main()使用if(primes[j]<limit){する <=必要があり、その中にelsewith 句が必要{break;}です。<Javaでうまくいったこと<=に驚いています。

そのままでは、<コードは 46340 より下の上位 46 個の素数を認識しません。それらは、配列の末尾1を超えて配置され、到達できないままになります。配列の末尾を超えて書き込むこと自体が悪いです。

1は、素数の 2 乗を素数として誤って認識し、5 から 46340 までの間に 46 個のそのような正方形があるためです。

于 2012-08-05T19:57:34.320 に答える
1 
while((double)x1/(double)x2 == (double)(x1/x2)){

それはほとんどの場合、悪い考えです。浮動小数点演算の精度が限られているため、数学的な意味では 2 つがまったく同じであるにもかかわらず、上記のテストで false が返される場合があります。

于 2012-08-05T16:49:06.020 に答える