c++ - Eratosthenes筛-主要因子

我只是写了以下内容，以利用筛子找到某个大于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;
}

最佳答案

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内部，checkNummber将等于numberToCheck;
for(unsigned long long int j=2;j<=checkNumber;j++)-此循环应在j<=root之后结束。这足以标记所有非素数。


如果您确实需要处理这么大的数字，请使用segmented sieve。

关于c++ - Eratosthenes筛-主要因子，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39338281/