c++ - 埃拉托色尼筛法 - 质因数

Question

我只是写了下面的代码来利用筛法找到大于 2 的某个自然数的最大质因数。

该程序构建、运行并适用于较小的测试值，但对于大于 1000000 的值只会崩溃。

我自己写了这个——并且相信它可能会非常低效——在发现筛子是关于什么之后。

你能提出改进建议吗？

谢谢。

//LARGEST PRIME FACTOR w/SIEVE OF ERATHOSTHENES
#include <iostream>
#include <math.h>

using namespace std;

unsigned long long int numberToCheck=0;

void sieve(unsigned long long int checkNumber)
{
    checkNumber=numberToCheck;
    unsigned long long int root=(int)(sqrt(checkNumber));
    unsigned long long int primeFlagger[checkNumber+1];

    for(unsigned long long int i=0;i<=checkNumber;i++)
    {
        primeFlagger[i]=1;
    }

    primeFlagger[0]=0;
    primeFlagger[1]=0;

    for(unsigned long long int j=2;j<=checkNumber;j++)
    {
        if(primeFlagger[j]==1)
        {
            for(unsigned long long int k=2;(k*j)<=checkNumber;k++)
            {
                primeFlagger[j*k]=0;
            }
        }
    }

    for(unsigned long long int l=checkNumber;l>=0;l--)
    {
        if(primeFlagger[l]==1)
        {
            if(checkNumber%l==0)
            {
                cout<<l<<" is the largest prime factor"<<endl;
                break;
            }
        }
    }
}

int main()
{
    cout<<"Largest prime factor less then or equal to? "<<endl;
    cin>>numberToCheck;
    cout<<endl;
    cout<<"Retrieving largest prime factor..."<<endl;

    sieve(numberToCheck);



    return 0;
}

Answer 1

你的数组 unsigned long long int primeFlagger[checkNumber+1];里面sieve功能太长。在全局范围内使用数组，在任何函数或动态内存分配之外。

此外，您不需要 unsigned long long .它是最大的整数数据类型，您只使用其中的一位。将类型更改为 bool 也会对您有所帮助。

还有其他问题:

• unsigned long long int root=(int)(sqrt(checkNumber)); - 如果数字真的很大，sqrt(checkNumber)可以溢出int ;
• unsigned long long int primeFlagger[checkNumber+1]; - checkNumber 的类型可能大于 std::size_t - 数组索引的类型且大于可分配的最大内存区域。你只是不能使数组大小为 unsigned long long。
• checkNumber=numberToCheck; - 你不需要这个。 numberToCheck其中已经作为参数传递给函数 checkNumber .里面sieve checkNumber 将等于 numberToCheck ;
• for(unsigned long long int j=2;j<=checkNumber;j++) - 这个循环应该结束 j<=root .这足以标记所有非质数。

如果您确实需要处理如此大的数字，请使用 segmented sieve .