可以看成問這個數的前面有幾個質數（含自己）

線性建表找出１０００００１前的所有質數

然後ｄｐ出每一項

```

#include <iostream>
#include <vector>
using namespace std;

const int MAX=1000001;
vector<int> prime;
void linear_sieve(){
bool sieve[MAX];
for(int i=2; i<=MAX; i++){
if(!sieve[i])
prime.push_back(i);
for(int j=0; i*prime[j]<MAX; j++){
sieve[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}

int main() {

linear_sieve();

int dp[MAX], primeNum=0;
dp[0]=1, dp[1]=1;

for(int i=2; i<MAX; i++){
while(primeNum<prime.size()-1 && prime[primeNum] < i+1) primeNum++;
dp[i] = dp[prime[--primeNum]-1] + 1;
//cout << i+1 << " = dp" << prime[primeNum] << " +1 = " << dp[i] << endl;;
}

int n;
while(cin >> n){
cout << dp[n-1] << '\n';
}
/*for(int i=0; i<100; i++){
cout << i+1 << ": " << dp[i] << '\n';
}*/

}

```