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

对编程一片赤诚的小吴

发布于 2024-01-23 15:26:52

1120

发布于 2024-01-23 15:26:52

一.思路分析

先来看看素数的性质：

素数又称质数，是指除了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;
}

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

数学