卡在下面的dp代码

Question

我写了下面的 dp 代码来求一个数的质因数。

#include <bits/stdc++.h>
#define max 1000001
using namespace std;
vector <int> prime;
vector<bool> isprime(max,true);
vector<bool> visited(max,false);
vector<int> data(max,-1);
void dp(int n,int last)
{
    if(n >= max || visited[n])
        return;
    visited[n] = true;
    for(int i = last;i<prime.size();i++)
    {
        if(n*prime[i] >= max || data[n*prime[i]] != -1)
            return;
        data[n*prime[i]] = prime[i];
        dp(n*prime[i],i);
    }
}
int main()
{
    isprime[1] = false;
    data[1] = 1;
    for(int i = 4;i<max;i += 2)
        isprime[i] = false;
    for(int i = 3; i*i< max;i += 2)
    {
        for(int j = i*i; j < max;j += i)
            isprime[j] = false;
    }
    prime.push_back(2);
    data[2] = 2;
    for(int i =3;i<max;i += 2)
        if(isprime[i])
        {
            prime.push_back(i);
            data[i] = i;
        }

    for(int i = 0;i<prime.size();i++)
    {
        dp(prime[i],i);
    }
        cout<<"...1\n";
    for(int i = 2;i<=8000;i++)
    {
        cout<<i<<" :- ";
        int temp = i;
        while(temp!= 1)
        {
            cout<<data[temp]<<" ";
            temp = temp/data[temp];
        }
        cout<<endl;
    }

    return 0;
}

这里，last是质数的最后一个索引n。但是当我将 max 更改为 10001 时，我遇到了分段错误，它运行完美。我不明白为什么会发生这种情况，因为使用的数据结构是一维向量，可以轻松保存高达 10^6 的值。

Answer 1

我使用 GDB 检查了你的程序。段错误发生在这一行：

if(n*prime[i] >= max || data[n*prime[i]] != -1)

在您第一次在 for 循环中调用 DP 时，您调用了 dp(2,0)，递归调用最终生成此调用：dp(92692,2585)。

92692 * 2585 = 239608820

这个数大于一个 32 位整数可以容纳的值，因此这两个数的整数相乘生成的 r 值溢出并变为负数。 nprime[i] 变为负数，因此上述循环的第一个条件失败，第二个条件被检查。 data[n * prime[i]] 被访问，并且由于 n*prime[i] 为负，您的程序访问无效内存和段错误。要解决此问题，只需在参数列表中将 n 更改为 long long 即可。

void dp(long long n, int last)

卡在下面的dp代码

Stuck in the following dp code

c++

algorithm

dynamic-programming

prime-factoring