求解100~200之间的素数

求解100~200之间的素数目录

文章目录

• 求解100~200之间素数目录
• 前言
• 一、素数是什么？
• 二、求解素数的方法
  • 1.常规方法
  • 2.优化方法
  • 3.另辟蹊径
• 总结

---

前言

对于很多人对求解素数存在一定的困惑，在这里，我将用一些方法为大家讲解我的理解，希望可以帮助大家。下面是求解100~200之间素数的方法

---

一、素数是什么？

素数：素数也称质数，素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。（PS：7=1*7，7为素数）

二、求解素数的方法

1.常规方法

代码如下（示例）：

#include<stdio.h>
//求解100~200之间的素数
int main()
{
	int i = 0;
	int j = 0;
	int sum = 0;                 //sum 计数，统计100~200之间的素数个数  
	for (i = 100; i <= 200; i++) //规定范围
	{
		for (j = 2; j < i; j++)  //素数的定义为只有两个因子：1和它本身
		{
			if (i % j == 0)      //如果i%j==0 说明j也是i的因子，不满足质数的条件
			{
				break;           //已经不满足的，跳出循环
			}
		}
		if (j == i)              //如果是质数，内循环中未进行break操作，j++到循环结束为i
		{
			printf("%d ", i);    //输出i
			sum++;               //总数加一
		}
	}
	printf("\nsum=%d\n", sum);
	return 0;
}

2.优化代码

优化代码1如下（示例）：

int main()
{
	int i = 0;
	int j = 0;
	int sum = 0;                 //sum 计数，统计100~200之间的素数个数  
	for (i = 101; i < 200; i+=2) //100,200为偶数不考虑，100~200中的偶数都不考虑每次加2，跳过2
	{
		for (j = 2; j < i; j++)  //素数的定义为只有两个因子：1和它本身
		{
			if (i % j == 0)      //如果i%j==0 说明j也是i的因子，不满足质数的条件
			{
				break;           //已经不满足的，跳出循环
			}
		}
		if (j == i)              //如果是质数，内循环中未进行break操作，j++到循环结束为i
		{
			printf("%d ", i);    //输出i
			sum++;               //总数加一
		}
	}
	printf("\nsum=%d\n", sum);
	return 0;
}

通过对素数定义的理解，明白偶数（不包括0，2）一定不是素数，在循环过程中，不在考虑偶数，可以大大的提高代码的运算速度。

---

for (i = 101; i < 200; i+=2) //100,200为偶数不考虑，100~200中的偶数都不考虑每次加2，跳过2
	{
		for (j = 2; j <= i/2; j++)  //素数的定义为只有两个因子：1和它本身,i/2为上届
		{
			if (i % j == 0)      //如果i%j==0 说明j也是i的因子，不满足质数的条件
			{
				break;           //已经不满足的，跳出循环
			}
		}
		if (j == i)              //如果是质数，内循环中未进行break操作，j++到循环结束为i
		{
			printf("%d ", i);    //输出i
			sum++;               //总数加一
		}
	}

 

	for (i = 101; i < 200; i+=2) //100,200为偶数不考虑，100~200中的偶数都不考虑每次加2，跳过2
	{
		for (j = 2; j <= sqrt(i); j++)  //素数的定义为只有两个因子：1和它本身,
		{
			if (i % j == 0)      //如果i%j==0 说明j也是i的因子，不满足质数的条件
			{
				break;           //已经不满足的，跳出循环
			}
		}
		if (j == i)              //如果是质数，内循环中未进行break操作，j++到循环结束为i
		{
			printf("%d ", i);    //输出i
			sum++;               //总数加一
		}
	}

 

3.另辟蹊径

用函数的方法，或者采用一种特殊的方法，见如下（）：

#include<stdio.h>
int main()
{
	int i = 0;
	int sum = 0;                 //sum 计数，统计100~200之间的素数个数  
	for (i = 101; i < 200; i+=2) //100,200为偶数不考虑，100~200中的偶数都不考虑每次加2，跳过2
	{
		if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0&&i%11!=0&&i%13!=0)  //因为2，3，5，7，11，13为质数
		{
			printf("%d ", i);
			sum++;
		}
	}
	printf("\nsum=%d\n", sum);
	return 0;
}

在100~200的范围中，如果可以整除质数，说明质数为其因子，不考虑其他数的原因是其他数拥有多个因子，质数只有两个因子，若整除质数都不等于0，说明包含的因子数只有1和它本身，则它一定是质数。

4.函数方法解决

#include<stdio.h>
#include<math.h>
int su(int a)             //需要返回一个判断数
{
	int i = 0;
	for (i = 2; i <= sqrt(a); i++) 
	{
		if (a % i == 0)
		{
			return 1;     //不是质数返回1
			break;        //直接结束循环，函数结束
		}
	}
}
int main()
{
	int i = 0;
	int sum = 0;
	for (i = 101; i < 200; i+=2)
	{
		if (su(i) != 1)
		{
			printf("%d ", i);
			sum++;
		}

	}
	printf("\nsum=%d\n",sum);
	return 0;
}

总结

在这个题目中，我们需要了解质数的定义，明白判断条件，结束条件是什么。求赞，求关注呀！