首页 > 代码库 > 每日一小练——求质数

每日一小练——求质数

2024-07-04 21:48:49   224人阅读

上得厅堂，下得厨房，写得代码，翻得围墙，欢迎来到睿不可挡的每日一小练！


题目：求质数


内容：

试编写一个程序，找出前N个质数。如果没有进一步要求，这不是难题。但在此希望从所知的、使用除法的方法中，用最快的办法来编写程序。


我的解法：上来没多想，打开vs2013就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就解决了！这个题目确实很简单，先看看常规解法吧！

#include <iostream>
#include <math.h>
#define endNum 200
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	bool isPrime(int x);
	cout << endNum << "以内的之所以素数为：" << endl;
	for (int i = 2; i < endNum; i++)
	{
		if (isPrime(i))
			cout << i << "  ";
	}
	getchar();
	return 0;
}

bool isPrime(int x)
{
	int endP = sqrt(x);
	bool rusult = true;
	for (int i = 2; i <= endP; i++)
	{
		if ((x % i) == 0)
		{
			rusult = false;
		}
	}
	return rusult;
}

实验结果是



不过题目中要求了思索除法范围内最快的算法，其实就是在循环中，减少以至不为质数的值的除法运算，比如2的倍数，3的倍数，和5的倍数。这样循环的递增就不是按照+1递增了，而已2,4,2,4....循环加法递增，这样可以减少循环三分之二的工作量。

改价算法如下

#include <iostream>
#include <math.h>
#define endNum 200
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	bool isPrime(int x);
	int addNum = 2;
	cout << endNum << "以内的之所以素数为(改进算法)：" << endl;
	cout << "2  3  5  ";
	for (int i = 7; i < endNum; )
	{
		if (isPrime(i))
			cout << i << "  ";
		addNum = 6 - addNum;
		i += addNum;
	}
	getchar();
	return 0;
}

bool isPrime(int x)
{
	int endP = sqrt(x);
	bool rusult = true;
	for (int i = 2; i <= endP; i++)
	{
		if ((x % i) == 0)
		{
			rusult = false;
		}
	}
	return rusult;
}

实验结果：



最后要感谢Clover_tjp同学提出的建议，我会在以后的每日一下练中加以改进，欢迎大家提出自己的意见哈！


欢迎大家加入每日一小练，嘿嘿！

每天练一练，日久见功夫，加油！


            -End-

参考文献：《c语言名题精选百则》


联系
我们