如何区分C语言中两种素数判定方法的区别？

本文共计1523个文字，预计阅读时间需要7分钟。

目录

1.什么是素数

2.素数的两种判断方法

   (1) 暴力法   (2) 筛法     - 埃拉托斯特尼筛法     - 欧几里得筛法     - 埃拉托斯特尼筛法

3.什么是素数

   素数又称质数，是一个大于1的自然数，除了1和它本身以外不再有其他因数。

目录

• 1.什么是素数
• 2.素数的两种判断方法
• （1）暴力法
• 从 2 到 √n
• 6n-1与6n+1
• （2）筛法
• 埃氏筛
• 欧拉筛

1.什么是素数

素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是素数也不是合数）。

在许多的程序设计题目中，都会涉及到素数的判断，那我们该如何有效判断素数呢？

2.素数的两种判断方法

（1）暴力法

从 2 到 √n

根据素数的定义，我们可以使用逐个试除的方式来判断素数，如果能为要判断的数找到一个除了1和自身以外的因数，那么它就是合数；反之，就是素数。

而这样的因数的范围必然在 2 ~ √n之间，所以我们便可以得到以下代码。