次の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までの値を簡単に保持できる1-dベクトルであるため、なぜこのようなことが起こっているのか分かりません。

Answer 1

GDBを使用してプログラムをチェックしました。セグメンテーション違反がこのラインで行われている：DP（92692、：最初に

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

今まであなたは、DP（2,0）を呼び出すループ、のためにあなたにDPに呼び出し、再帰呼び出しは最終的に、この呼び出しを生成します2585）。

92692 * 2585 = 239608820 

この数値は32ビット整数が保持できるよりも大きいため、これらの2つの数値の整数倍で生成されたr値はオーバーフローして負になります。 nprime [i]が負になるので、上記のループの最初の条件は失敗し、2番目の条件がチェックされます。 data [n * prime [i]]はアクセスされ、n * prime [i]は負であるため、プログラムは無効なメモリーとsegfaultにアクセスします。これを修正するには、パラメータリストでnをlong longに変更するだけで問題ありません。

void dp(long long n, int last)