（创建页面，内容为“若一个正整数无法被除了1和它自身以外的任何自然数整除，则称该数为'''素数（Prime number）'''，或称'''质数'''。 在整个自然数集合中，素数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的素数大约有<math>\frac{N}{\ln N}</math>”） |
无编辑摘要 |
||
| 第1行： | 第1行： | ||
若一个正整数无法被除了1和它自身以外的任何自然数整除，则称该数为'''素数（Prime number）'''，或称'''质数'''。 | 若一个正整数无法被除了1和它自身以外的任何自然数整除，则称该数为'''素数（Prime number）'''，或称'''质数'''。 | ||
在整个自然数集合中，素数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的素数大约有<math>\frac{N}{\ln N}</math> | 在整个自然数集合中，素数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的素数大约有<math>\frac{N}{\ln N}</math>个。 | ||
== 质数的判定 == | |||
最简单的方法就是试除法，它作为最简单也最经典的确定性算法，是我们经常会使用的方法。 | |||
<syntaxhighlight lang="c" line> | |||
int is_prime(n) { | |||
if (n < 2) | |||
return 0; | |||
for (int i = 2; i < sqrt(n); ++i) | |||
if (n % i == 0) | |||
return 0; | |||
return 1; | |||
} | |||
</syntaxhighlight> | |||
2022年2月21日 (一) 15:35的版本
若一个正整数无法被除了1和它自身以外的任何自然数整除，则称该数为素数（Prime number），或称质数。
在整个自然数集合中，素数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的素数大约有[math]\displaystyle{ \frac{N}{\ln N} }[/math]个。
质数的判定
最简单的方法就是试除法，它作为最简单也最经典的确定性算法，是我们经常会使用的方法。
int is_prime(n) {
if (n < 2)
return 0;
for (int i = 2; i < sqrt(n); ++i)
if (n % i == 0)
return 0;
return 1;
}