Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

质数的判定

WalterJ726 2020-02-16 22:55:00 阅读数:18 评论数:0 点赞数:0 收藏数:0

ACwing866. 试除法判定质数

素数定义:一个数n,如果不能被[2,n-1]内的所有数整除,n就是素数。

当然,我们可以把范围从[2,n-1]缩小到[2,根号n]

证明如下:

假设n=a*b,有min(a,b) <= 根号n ,令a <= b.只要检查[2,根号n]内的数。如果n不是素数,就可以找到一个a。如果不存在这个a,那么[根号n,n-1]内也不存在b

算法如下:

bool is_prime(int n)
{
if (n <= 1)
return false; // 1不是素数
for (int i = 2; i * i <= n; i++) // 比for (int i = 2; i <= sqrt(n); i++) 更好
if (n % i == 0) // 能整除,不是素数
return false;
return true;
}
版权声明
本文为[WalterJ726]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/WalterJ726/p/12319305.html