欧拉函数：修订间差异

2026年5月20日 (三) 18:24的最新版本

重定向到：

@@ 第1行： / 第1行： @@
-==线性筛求欧拉函数==
+#REDIRECT [[06-数学相关/03-欧拉函数]]
+[[Category:三三文档]]
-<syntaxhighlight lang="cpp" line>
-const int MAXN = 40000;
-bool p[MAXN + 5];
-int phi[MAXN + 5];
-vector<int> pri;
-// 筛出 1~n 中的每个数是否为质数
-// 顺带求出所有欧拉函数
-void get_primes(int n)
-{
-    for (int i = 1; i <= n; i++)
-        p[i] = true;
-    p[0] = p[1] = false;
-    phi[1] = 1;
-    for (int i = 2; i <= n; i++)
-    {
-        if (p[i])
-        {
-            pri.push_back(i);
-            phi[i] = i - 1;
-        }
-        for (int j = 0; j < pri.size(); j++)
-        {
-            // i*pri[j]
-            if (1LL * i * pri[j] > n)
-                break;
-            p[i * pri[j]] = false;
-            if (i % pri[j] == 0)
-            {
-                phi[i * pri[j]] = phi[i] * pri[j];
-                break;
-            }
-            else
-                phi[i * pri[j]] = phi[i] * (pri[j] - 1);
-        }
-    }
-}
-</syntaxhighlight>