当前位置：网站首页>埃氏筛选法：统计素数个数

埃氏筛选法：统计素数个数

2022-08-09 21:35:00 【哆啦k梦0219】

埃筛法的核心思想：当我们找到一个素数，那么这个数小于n的所有倍数肯定都不是素数，同时进行标记。

#include <iostream>
using namespace std;

class Solution {
public:
	bool isprime(int n)
	{
		for (int i = 2; i*i <= n; i++)
		{
			if (n % i == 0)
				return false;
		}
		return true;
	}
	int cout_prime(int n)
	{
		int* tag = new int[n] {0};//0代表是素数
		int count = 0;
		for (int i = 2; i < n; i++)
		{
			if (tag[i]==0)
			{
				count++;
				for (int j = i * i; j < n; j += i)//j+=i实现i的递增
				{
					tag[j] = 1;
				}
			}
		}
		return count;
	}
};
int main()
{
	Solution s;
	int n = s.cout_prime(100);
	cout << n;
	return 0;
}

以上代码中重点看这段代码：

for (int j = i * i; j < n; j += i)//j+=i实现i的递增
{
    tag[j] = 1;
}

这段代码原版是j = i*2;但由于每次i对递增会出现重复标记的情况，故对代码进行优化，每次以i本身为倍数进行递增，提高效率。

原网站

版权声明
本文为[哆啦k梦0219]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_53986026/article/details/126240050

边栏推荐

猜你喜欢

随机推荐