我的埃拉托色尼筛法程序发生了什么变化？

Question

我正在尝试解决一个具有挑战性的问题，即对 200 万以下的所有素数求和。完全清楚天真的方法会花费太长时间，我决定用一个计数器来实现埃拉托色尼筛法来记录总和。它最多适用于 512500，之后我收到此错误：

输入大小是否太大以至于代码无法处理？如果是这样的话，我该如何改进我的代码来避免这个错误。如果那不可能，什么是更好的算法来实现这些目的？

这是我的 header 代码：

#ifndef NUMBERSIEVE_H
#define NUMBERSIEVE_H


class NumberSieve
{
    public:
        NumberSieve();
        virtual ~NumberSieve();
        int EratosthenesSieve(int num);
    private:
        void SetSieve(int nums[],int Size);
        int current_prime;
        int current_prime_address;
        void updateSieve(int nums[],int Size,int start);
        bool updateCurrentPrime(int nums[],int Size,int start);
        bool notComplete;
        void printSieve(int nums[],int Size);
        int primeSum;
};

#endif // NUMBERSIEVE_H

这是我的实现文件：

#include "NumberSieve.h"
#include <cstdlib>
#include <iostream>
NumberSieve::NumberSieve()
{
    //ctor
}

NumberSieve::~NumberSieve()
{
    //dtor
}
void NumberSieve::SetSieve(int nums[],int Size)
{
    for(int i=0;i<Size;i++)
    {
        nums[i]=(i+1);
    }
    nums[0]=0;//Sets the first composite number 1 to 0. We use 0 as an analogy for "crossing out numbers in the Sieve".
}
void NumberSieve::updateSieve(int nums[],int Size,int start)
{
    int CURRENT_PRIME=nums[start];
    for(int i=start;i<Size;i++)
    {
        if(nums[i]%CURRENT_PRIME==0)
        {
            nums[i]=0;
        }
    }
    nums[start]=CURRENT_PRIME;
}
bool NumberSieve::updateCurrentPrime(int nums[],int Size,int start)
{
    for(int i=start+1;i<Size;i++)
    {
        if(nums[i]!=0)
        {
            primeSum+=nums[i];
            current_prime=nums[i];
            current_prime_address=i;
            return true;
        }
    }
    return false;
}
void NumberSieve::printSieve(int nums[],int Size)
{
    for(int i=0;i<Size;i++)
    {
        std::cout<<nums[i]<<std::endl;
    }
}
int NumberSieve::EratosthenesSieve(int num)
{
    int Eratosthenes[num];
    int primeSum=0;
    SetSieve(Eratosthenes,num);
    current_prime=2;
    primeSum+=2;
    current_prime_address=1;
    updateSieve(Eratosthenes,num,current_prime_address);
    notComplete=updateCurrentPrime(Eratosthenes,num,current_prime_address);
    while(notComplete)
    {
        updateSieve(Eratosthenes,num,current_prime_address);
        notComplete=updateCurrentPrime(Eratosthenes,num,current_prime_address);
    }
    return primeSum;
}

Answer 1

我最好的猜测是 Whosebug，因为：

int Eratosthenes[num];

改为尝试从免费商店获取它：

int* Eratosthenes = new int[num]

相应地更新其余代码

如果您不习惯使用指针，向量可能是另一种选择。

我的埃拉托色尼筛法程序发生了什么变化？

What is Happening to my Sieve of Eratosthenes Program?

c++

codeblocks