Loading... # Function -朴素筛法求素数 **原题：** > **One day, Little Y came cross a function that confused her a lot.** > $ f(n) = \begin{cases} 1, & n \in \{1\} \bigcup \operatorname{Prime} \\ p\,f(p^{k-2}), & n = p^k ~ (p \in \operatorname{Prime}; ~ k > 1) \\ f(p_1^{e_1})\prod_{i=2}^r {p_i}^{e_i}, & n = \prod_{i=1}^r {p_i} ^ {e_i} ~ (p_1 < p_2 < \cdots < p_r; ~ p_i \in \operatorname{Prime}; ~ r \ge 2) \end{cases}$ > Now Little Y is interested in $\sum_{i=1}^n f(i)$. Can you help her? **Input** > One line contains one integer denoting $n ~ (1 \le n \le {10}^{7})$. **Output** > One line, the number denoting the answer. **Sample 1** | **Input** | **Output** | | ----------- | ------------ | | `10` | `20` | **Sample 2** | **Input** | **Output** | | ----------- | ------------ | | `100` | `1487` | **Note** **For the first sample, ***f*(1)=1, *f*(2)=1, *f*(3) = 1*, f*(4)=2, f(5) = 1*, *f*(6)=3, f*(7)=1, f(8) = 2, *f*(9)=3, f(10) = 5. It is guaranteed that the answer will always be less than $2^{64}-12$. Little Y wonders whether you can solve *n* up to ${10}^{10}$. 涉及知识 质因数 ， 线性筛，唯一分解定理 第一次在学长的帮助下读懂题后按照自己敲下代码，发现超时，后来才发现朴素筛法是这么一回事 **超时代码：** ``` #include <cmath> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const ll maxn = 1e7 + 10; bool vis[maxn]; vector<ll> prime; bool is_prime(int x); void find_prime(int n); ll f(int x); ll quick_multy(ll x, int n); int main(void) { // freopen("ain.txt", "r", stdin); // freopen("aout.txt", "w", stdout); // int x, n; // scanf("%d %d", &x, &n); // printf("%lld\n", quick_multy(x, n)); int n; scanf("%d", &n); find_prime(n); // for (int i = 0; i < prime.size(); ++ i) { // printf("%lld\n", prime[i]); // } // for (int i = 1; i <= n; ++i) { // printf("%d\n", vis[i]); // } ll sum = 0; for (int i = 1; i <= n; ++ i) { if (vis[i] == true) { // printf("f(%d) = %d\n", i, f(i)); sum += f(i); } else { sum += 1; // printf("f(%d) = %d\n", i, 1); } } printf("%lld\n", sum); // printf("程序执行完成\n"); return 0; } void find_prime(int n) { memset(vis, false, sizeof(vis)); prime.push_back(1); for (ll i = 2; i <= n; ++ i) { if (!vis[i] && is_prime(i) == true) { ll cnt = 2; while (cnt * i < maxn) { vis[cnt * i] = true; ++ cnt; } prime.push_back(i); } } } bool is_prime(int x) { bool flag = true; if (x == 1) flag = false; int sqr = (int)sqrt(x * 1.0); for (int i = 2; i <= sqr; ++ i) { if (x % i == 0) { flag = false; break; } } return flag; } ll f(int x) { vector<pair<int, int>> fac; int cnt = 1, temp = x; // printf("这个数是：%d\n", x); while (cnt < prime.size() && temp != 1) { if (temp % prime[cnt] == 0) { // printf("%d %d\n", prime[cnt], temp); fac.push_back(make_pair(prime[cnt], 0)); while (temp % prime[cnt] == 0) { temp /= prime[cnt]; fac[fac.size() - 1].second ++; } } ++ cnt; } // printf("调用函数\n"); // printf("fac的长度：%lld\n", fac.size()); // printf("%d的因数\n", x); // for (int i = 0; i < fac.size(); ++i) { // printf("%d %d\n", fac[i].first, fac[i].second); // } if (fac.size() == 1) { return quick_multy(fac[0].first, fac[0].second / 2); } else { ll ret = (ll)x * quick_multy(fac[0].first, fac[0].second / 2); return ret / quick_multy(fac[0].first, fac[0].second); } // return x; } ll quick_multy(ll x, int n) { ll ret = 1, mul = x; while (n > 0) { if (n & 1) { ret *= mul; } mul *= mul; n >>= 1; } return ret; } ``` **完美代码：** ``` #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const ll maxn = 1e7 + 10; bool st[maxn] = {false}; ll f[maxn], prime[maxn]; ll get_prime(int x); ll quick_multy(ll x, int n); int main(void) { // freopen("ain.txt", "r", stdin); // freopen("aout.txt", "w", stdout); ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n; scanf("%d", &n); printf("%lld\n", get_prime(n)); return 0; } ll get_prime(int n) { int cnt = 0; f[1] = 1; for (int i = 2; i <= n; ++ i) { if (!st[i]) { // st[i] = true; prime[cnt ++] = i; f[i] = 1; } int index = 0; while (i * prime[index] <= n) { ll temp = i, num = 1, p = prime[index]; while (temp % p == 0) { temp /= p; ++ num; } st[i * p] = true; int e = (num + 1) / 2; f[i * p] = i * p / pow(p, e); if (i % p == 0) break; ++ index; } } ll res = 0; for (int i = 1; i <= n; ++ i) { res += f[i]; } return res; } ``` [**朴素筛法求素数 —— 模板**](%5B%E5%B8%B8%E7%94%A8%E4%BB%A3%E7%A0%81%E6%A8%A1%E6%9D%BF4%E2%80%94%E2%80%94%E6%95%B0%E5%AD%A6%E7%9F%A5%E8%AF%86%20-%20AcWing%5D(https://www.acwing.com/blog/content/406/)) ``` int primes[N], cnt; // primes[]存储所有素数 bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int n) { for (int i = 2; i <= n; i ++ ) { if (st[i]) continue; primes[cnt ++ ] = i; for (int j = i + i; j <= n; j += i) st[j] = true; } } ``` **参考资料** [常用代码模板4——数学知识 - AcWing](https://www.acwing.com/blog/content/406/) 最后修改：2022 年 07 月 17 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏
