-1

我正在参加UVA 在线编程竞赛，并且正在研究 UVA 583（主要因素）的解决方案。

我最近为此做了一个 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 
while((double)x1/(double)x2 == (double)(x1/x2)){

这几乎总是一个坏主意。由于浮点运算的精度有限，您最终可能会遇到在数学意义上两者完全等价的情况，但上面的测试结果为假。

于 2012-08-05T16:49:06.020 回答
1

在您的factorize(int x1)，就在上面while，添加if (x2*x2 > x1) break;.

在你的main(),if(primes[j]<limit){应该使用 <=并且它应该有else子句 with {break;}。<代替<=我很惊讶它在 Java 中对你有用。

实际上，在<那里，您的代码无法识别 46340 以下的前 46 个素数 - 它会将它们放在数组末端1之后，它们仍然无法触及。写过去数组的结尾本身就是不好的。

1那是因为它错误地将素数的平方识别为素数，并且在 5 到 46340 之间有 46 个这样的平方。

于 2012-08-05T19:57:34.320 回答