-4

これは、数値の最大の素因数を見つける必要があります..しかし、機能していません..答えは6857のはずですが、688543を返しています..

int isPrime(unsigned long int n)
{
    for(unsigned long int i=2;i*i<(n);i++)
    {
        if(n%i==0)
        {
            return 0;
            break;
        }
    }
    return 1;
}

int main()
{
    unsigned long int num=600851475143;
    unsigned long int max=2, i=2;
    while(num!=1)
    {
        if(num%i==0 && isPrime(i))
        {
            max=i;
            num/=i;
            i--;
        }

        i++;
    }
    cout<<max;
    return 0;
}

前もって感謝します：）

4

2 に答える 2

0

unsigned longあなたのシステムではどうやら32ビットなので、そうでnumは600851475143なく、600851475143 mod 1<<32どちらが3851020999. 688543はこの数の最大の素因数であるため、少なくともアルゴリズムは正しく機能しているように見えます。

コンパイラとシステムの組み合わせの型の最大範囲を調べてから、適切なものを選択してください。

于 2013-10-10T14:53:04.370 に答える
0

他の問題の中でも、これは多数の問題になります。

for(unsigned long int i=2;i*i<(n);i++)

i*iunsigned long大きい数値の場合、 (コンパイル対象のシステムでは 32 ビットのように見えます)のオーバーフローが発生します。

切り替えることで修正できます：

for (unsigned long int i = 2; i <= sqrt(n); ++i)

nオーバーフローしない限りsqrt(n)有効です。ただし、unsigned long long32 ビット整数の境界に非常に近い数値を使用する場合は、using に切り替えることをお勧めします。

于 2013-10-10T14:57:45.960 に答える