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

Question

这是我针对半素数计数问题的解决方案，该解决方案对于小型和中型输入是正确的，但会导致大型测试用例的段错误。

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;
}

Answer 1

在这一部分中，对于 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;
        }
    }