数论专题-质数与判断质数

2025-10-17 07:16:29

本篇博客是【数论专题】系列的第 \(1\) 篇，希望大家多多支持。

质数

质数，也称素数。

若一个数 \(p\) 为质数，则它的因数只有 \(1, p\)。

例如 \(2, 3\) 都是质数。

特别的，\(1\) 不是质数。

判断质数

判断一个数 \(p\) 是否是质数，需要判断 \(2\sim \sqrt p\) 是否有数是 \(p\) 的因数，若有，则说明 \(p\) 有除了 \(1, p\) 以外的因数，\(p\) 不是质数，否则，\(p\) 是质数。

时间复杂度 \(O(\sqrt p)\)。

bool is_prime(int p)

{

if(p == 1) return false;//特判，1 不是质数

for(int i = 2;i * i <= p;i ++)

if(p % i == 0) return false;//判断 p 是否有除了 1,p 以外的因数，如果有，p 不是质数

return true;//如果 p 只有 1,p 两个因数，p 是质数

}