时间戳

首页 > 解决方案 > 质数超过 600 万

c++ - 质数超过 600 万

问题描述

我在 Hackerrank 中解决一个问题，问题是在一个范围内找到素数计数。由于使用常规方法面临超时，我使用了埃拉托色尼筛。除了两个隐藏的测试用例外，大多数测试用例都有效。我在 GDB 编译器中运行代码，发现代码只支持高达 600 万的值。我该怎么办？代码如下：

#include<cstring>
#include<cstdio>
#include <iostream>
#include <algorithm>
using namespace std;


void SieveOfEratosthenes(unsigned long long int a,unsigned long long int b) 
{ 
    unsigned long long int count=0; 
    bool prime[b+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (unsigned long long int p=2; p*p<=b; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            for (unsigned long long int i=p*p; i<=b; i += p) 
                prime[i] = false; 
        } 
    } 
  
    for (unsigned long long int p=a; p<b; p++) 
       if (prime[p] &&p!=1) 
           count++;
    cout<<count;
          
} 
  
int main() 
{ 
    unsigned long long int a,b;
    cin>>a>>b;
    SieveOfEratosthenes(a,b); 
    return 0; 
}

标签： c++primesmemsetsieve-of-eratostheneslargenumber

解决方案

看起来像一个经典的堆栈溢出。bool prime[b+1];在堆栈上分配，并且您已达到限制。

如果这是在 Linux 上运行的，那么最大允许的堆栈大小通常总共约为 8MB 或更小，所以你很有可能刚刚超过了这个值。

将其移出堆栈，或执行位打包而不是完整的bool，它应该可以再次正常工作。

推荐阅读