gpt4 book ai didi

c++ - 素数600万以上

转载 作者:行者123 更新时间:2023-12-01 15:10:16 25 4
gpt4 key购买 nike

我在Hackerrank中解决了一个问题,问题是要找到一个范围内的素数计数。由于使用常规方法会面临超时问题,因此我使用了Eratosthenes的Sieve。除了两个隐藏的测试用例之外,大多数测试用例都有效。我在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;
}

最佳答案

看起来像经典堆栈溢出。 bool prime[b+1];是在堆栈上分配的,您已经达到了极限。
如果此程序在Linux上运行,则允许的最大堆栈大小通常总计约为8MB或更小,因此很有可能您刚刚超过了该大小。
将其移出堆栈,或执行位打包而不是完整的bool,它应该又可以正常工作了。

关于c++ - 素数600万以上,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63226796/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com