C/C++教程

C语言/C++判断质数剪枝优化【简单易懂,代码可以直接运行】

本文主要是介绍C语言/C++判断质数剪枝优化【简单易懂,代码可以直接运行】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

C语言/C++判断质数【简单易懂,代码可以直接运行】

**一个大于 1 的自然数,如果除了 1 和它自身外,不能被其他自然数整除则称该数为质数。

例如 7 就是一个质数,因为它只能被 1 和 7 整除。

现在,给定你 N 个大于 1 的自然数,请你依次判断这些数是否是质数。

输入格式
第一行包含整数 N,表示共有 N 个测试数据。

接下来 N 行,每行包含一个自然数 X。

输出格式
每个测试用例输出一个结果,每个结果占一行。

如果测试数据是质数,则输出 X is prime,其中 X 是测试数据。

如果测试数据不是质数,则输出 X is not prime,其中 X 是测试数据。**

时空限制:
1≤N≤100 ,
1<X≤107

代码如下:

#include<iostream>
using namespace std;
int main()
{
	int i,n,num,flag;
	cin>>n;
	while(n--)
	{
		cin>>num;
		flag = 0;
		for(i = 2;i*i <= num;i++)//使用优化时,需要设置<=而不是<,如果是小于的话,完全平方数排除不成功 
		{
			if(num % i == 0)
			{
				flag = 1;
				break;
			}
		}
		if(flag == 1)
		{
			cout<<num<<" is not prime"<<endl;
		}
		else
		{
			cout<<num<<" is prime"<<endl;
		}
		
}
}

这里面i*i<=num是优化部分,i = 根号n,即在i之前就可以将num的所有的因数遍历一遍,这样就可以少遍历一半的数据,可以避免超时问题
对于这个优化举一个具体的例子,以16为例,4是16的平方根,在4之前(包括是)16的因素有1 2 4,其中既然2是16的公因数那么16/2=2,依然是16的公因数,所以不用去遍历8就可以得到8是16公因数的结论
在这里插入图片描述
优化的时间十分明显,极大地降低了时间复杂度

点个

这篇关于C语言/C++判断质数剪枝优化【简单易懂,代码可以直接运行】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!