卡在下面的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) 

在你第一次打電話給DP在for循環中，在那裏你調用DP（2,0），遞歸調用最終產生這一呼籲：DP（92692， 2585）。

92692 * 2585 = 239608820 

此數量大於32位的整數可以容納大，因此通過這兩個數字溢出的整數乘法產生的r值和變負。 nprime [i]變爲負值，所以上述循環的第一個條件失敗，第二個條件被檢查。數據[n * prime [i]]被訪問，並且由於n * prime [i]是負數，您的程序將訪問無效內存和段錯誤。要解決這個問題，只需在參數列表中將n改爲很長的一段，並且應該沒問題。

void dp(long long n, int last)