Coincé dans le code suivant dp

Question

J'ai écrit le code suivant dp pour trouver les facteurs premiers d'un nombre.

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

Ici, last est le dernier indice du nombre premier n. Mais je reçois un défaut de segmentation pour cela, quand je change max en 10001, il fonctionne parfaitement. Je ne comprends pas pourquoi cela se produit puisque les structures de données utilisées sont des vecteurs 1-d qui peuvent facilement contenir des valeurs allant jusqu'à 10^6.

Answer 1

J'ai vérifié votre programme en utilisant GDB. Le segfault a lieu à cette ligne:

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

Dans votre premier appel jamais DP dans votre boucle, où vous appelez dp (2,0), les appels récursifs éventuellement générer cet appel: dp (92692, 2585).

92692 * 2585 = 239608820 

Ce nombre est supérieur à un nombre entier de 32 bits peut contenir, de sorte que la valeur r généré par la multiplication du nombre entier de ces deux nombres déborde et devient négatif. nprime [i] devient négatif, donc votre première condition de la boucle ci-dessus échoue, et la seconde est vérifiée. data [n * prime [i]] est accessible, et comme n * prime [i] est négatif, votre programme accède à la mémoire et aux erreurs de segment invalides. Pour résoudre ce problème, il vous suffit de modifier n dans votre liste de paramètres et cela devrait fonctionner.

void dp(long long n, int last)