80722 - 同测活动第4场阅读程序3
统计题目(材料题)
（3）
01 #include <bits/stdc++.h>
02 #define INF 0x3f3f3f3f
03 using namespace std;
04 const int N = 1e6 + 5;
05 int dp[N];
06 bool vis[N];
07 vector<int> prime;
08 int main() {
09 memset(dp, INF, sizeof(dp));
10 memset(vis, false, sizeof(vis));
11 dp[1] = 0;
12 for (int i = 2; i <= 1000000; i++) {
13 if (!vis[i])
14 prime.push_back(i);
15 for (int p : prime) {
16 if (p * i > 1000000)
17 break;
18 vis[p * i] = true;
19 if (i % p == 0)
20 break;
21 }
22 }
23 for (int i = 1; i <= 1000000; i++) {
24 dp[i + 1] = min(dp[i + 1], dp[i] + 1);
25 for (int p : prime) {
26 if (p * i > 1000000)
27 break;
28 dp[p * i] = min(dp[p * i], dp[i] + 1);
29 }
30 }
31 int n;
32 while (cin >> n)
33 cout << dp[n] << endl;
34 return 0;
35 }
假设输入不超过 $10^{6} $的正整数，完成下面的判断题和单选题
关注我们
