萌新小白必做题（2）找素数

素数"/>

萌新小白必做题（2）找素数

一.思路分析

先来看看素数的性质：

素数又称质数，是指除了1和本身外没有其它因数的自然数。素数有许多有趣的性质和应用，例如可以用于加密算法和数学证明等。比如2、3、5、7等都是素数，而4、6、8、9等则不是素数。素数的研究是数论领域的重要课题之一，也是现代密码学和计算机科学中的重要基础。

找素数，最常见的有2种方法：

暴力法

从2开始遍历，到n结束，如果其中的数存在能够整除n的，就不是素数。

int main()
{int n = 0;scanf("%d", &n);for (int i = 2; i < n; i++){if (n % i == 0){printf("no\n");return;}}printf("yes\n");return 0;
}

2.我们在暴力法上再进行修改一下，我们设两个整数a和b，如果不是质数的话，整数x就可以写成 x=a * b 比如：
36=2 * 18
36=3 * 12
36=4 * 9
36=6 * 6
如果整数x为质数，那么就不可能写成 x = a * b的形式。所以如果整数x无法被小于等于x的平方根的质数整除，则x为质数。
因此，我们可以在第四种方法上改造一下，就是在第二层for循环，从数组的第一个元素出发，每一个都写成平方，直到平方大于整数x退出循环。

int main()
{int n = 0;scanf("%d", &n);for (int i = 2; i < sqrt(n); i++){if (n % i == 0){printf("no\n");return;}}printf("yes\n");return 0;
}