咨询1到n中约数和为质数的整数个数的高效求解方法

核心结论：仅素数幂可能满足条件 #

约数和函数σ(n)是积性函数，若n包含两个不同素因子p和q，则σ(n)=σ(p^a)*σ(q^b)，两个因子均大于1，乘积必为合数。因此只有素数幂x=p^k（p为素数，k≥1）才可能满足σ(x)是质数。

分析σ(p^k)为质数的条件 #

σ(p^k)=1+p+p²+…+p^k=(p^(k+1)-1)/(p-1)，该数为质数的必要条件是：

• k+1必须是素数：若k+1为合数，设k+1=ab（a,b>1），则σ(p^k)可分解为两个大于1的因子乘积，必为合数。令q=k+1（q为素数），则σ(p^k)=(p^q -1)/(p-1)，需验证该数是否为质数。

分情况讨论

情况1：p=2（偶素数）

此时σ(2^(q-1))=2^q -1，这是梅森数。梅森数为质数的必要条件是q为素数（非充分）。我们只需枚举所有满足2^(q-1)≤n的梅森素数对应的q即可。

例如n=1e9时，符合条件的q有2、3、5、7、13、17、19，对应x为2、4、16、64、4096、65536、262144，共7个。

情况2：p为奇素数，q为素数（q≥3）

q=2时，σ(p^1)=1+p是大于2的偶数，必为合数，故无需考虑。对于q≥3：

• 若p≡1 mod q，则σ(p^(q-1))=1+p+…+p^(q-1)≡q*1≡0 mod q，且该数大于q，必为合数，因此p≡不1 mod q是必要条件。
• 即使满足上述条件，仍需验证(p^q -1)/(p-1)是否为质数。

针对不同q，计算p的上限：

• q=3：x=p²≤n → p≤√n，统计奇素数p满足p²+p+1是质数；
• q=5：x=p^4≤n → p≤n^(1/4)，统计奇素数p满足p^4+p^3+p^2+p+1是质数；
• q=7：x=p^6≤n → p≤n^(1/6)，统计奇素数p满足p^6+p^5+p^4+p^3+p^2+p+1是质数；
• q≥11：x=p^(q-1)≤n的p上限快速缩小（如q=11时，n=1e9的p上限约为7），只需枚举少量奇素数验证即可。

高效实现步骤 #

1. 处理情况1：枚举已知的梅森素数对应的q，判断2^(q-1)≤n，统计数量；
2. 处理情况2：
   • 对每个素数q≥3，计算p的上限m=floor(n^(1/(q-1)))；
   • 用筛法生成≤m的奇素数；
   • 对每个素数p，用米勒-拉宾素性测试验证(p^q -1)/(p-1)是否为质数，统计符合条件的x=p^(q-1)数量。

时间复杂度 #

• 情况1：O(1)，已知梅森素数数量极少；
• 情况2：筛法时间O(m log log m)（m最大为√1e9=31622，耗时可忽略），米勒-拉宾测试对1e18以内的数可通过固定基保证准确性，单个数测试耗时O(log³n)，整体效率极高，可轻松处理n=1e9的场景。

内容的提问来源于stack exchange，提问作者Nguyen Tran Tung