题解 | #质数因子#埃氏筛+最大质因子性质

从i = 2开始遍历的时候，使用如下两个方法对代码进行优化：

一个正整数的质因子，最多只有一个大于其平方根。

证明：假设有超过一个质因子大于其平方根，那么二者相乘一定大于该数。得证。

如果找到一个质因子，那么该质因子的2倍、3倍...都不是质因子。

#include <bits stdc++.h>

using namespace std;

//constexpr long long N = 1e10 + 10;
//bool st[N];
unordered_map<long, bool> st;

inline void solve(long &amp;n)
{
    for (long i = 2; i &lt;= (long)sqrt(n); i++) {
        for (;!st[i] &amp;&amp; n % i == 0;) {
            cout &lt;&lt; i &lt;&lt; ' ';
            n /= i;
            for (long j = i + i; j &lt;= (long)sqrt(n); j += i)
                st[j] = true;
        }
    }
    if (n != 1) cout &lt;&lt; n &lt;&lt; ' ' &lt;&lt; endl;
}

int main()
{
    cin.tie(nullptr)-&gt;sync_with_stdio(false);
    long n;
    for (; cin &gt;&gt; n; st = {})
        solve(n);
    return 0;
}

注意

如果存在一个质因子比原 n 的开方大，那么最后一次执行 n /= i后，i 超过 sqrt(n)退出循环，此时的 n 一定是原 n 的约数，且如果他不是1的话，一定是个质数。</long,>