gpt4 book ai didi

c++ - Codility 代码导致段错误

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:45:55 25 4
gpt4 key购买 nike

这是我对计数半素数可修正性问题的解决方案,它适用于中小型输入,但会导致大型测试用例的段错误。

https://codility.com/demo/results/demo8JU794-FC7/

这通常发生在无效指针等情况下。但是我在这里看不到任何可能导致此类行为的内容。

您能发现代码中的任何错误吗?

vector<int> solution(int N, vector<int> &P, vector<int> &Q) {

int M = P.size();

// Use sieve of eratosthenes to find prime numbers within range 0 to N
vector<int> sieve(N+1);
sieve[0] = sieve[1] = 0;

for (int i = 2; i <= N; ++i)
{
if (sieve[i] == 0)
{
int k = i * i;
while(k <= N)
{
// For each non prime store its lowest prime divisor.
sieve[k] = i;
k += i;
}
}
}

vector<int> answer(M);

for (int i = 0; i < M; ++i)
{
// Count semiprimes for each range (P[i], Q[i])
int count = 0;

for(int j = P[i]; j <= Q[i]; ++j)
{
// If a number is divisible by prime and the result of this division is also a prime
// Then it's a semiprime.
if (sieve[j] != 0 && sieve[j / sieve[j]] == 0)
{
count++;
}
}
answer[i] = count;
}

return answer;
}

最佳答案

在这部分,对于 N = 50000,k = i * i 的结果溢出了一个 int,这就是段错误的原因。

    if (sieve[i] == 0)
{
int k = i * i;
while(k <= N)
{
// For each non prime store its lowest prime divisor.
sieve[k] = i;
k += i;
}
}

关于c++ - Codility 代码导致段错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21946344/

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