a035. 肺部麻糬數列
| From: [223.136.233.188] |
發表日期
:
2020-03-21 01:40
可以看成問這個數的前面有幾個質數(含自己)
線性建表找出1000001前的所有質數
然後dp出每一項
```
#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'; }*/ }
```
|