质数——朴素筛

最新推荐文章于 2024-09-05 19:17:28 发布

菜狗原来是我自己

最新推荐文章于 2024-09-05 19:17:28 发布

阅读量155

点赞数

分类专栏：数论文章标签：算法

本文链接：https://blog.csdn.net/pythpnhh/article/details/119969837

版权

数论专栏收录该内容

4 篇文章

订阅专栏

朴素筛

文章目录

朴素筛
一、朴素筛是什么？
二、应用
- 1.原题
- 2.题解实现
总结

一、朴素筛是什么？

筛除一个序列中非的质数的数

二、应用

1.原题

在这里插入图片描述

2.题解实现

代码如下（示例）：
在这里插入图片描述

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void get_prime(int n)
{
	for(int i = 2; i <= n; i++)
	{
		if(!st[i])
		{
			primes[cnt++] = n;
			for(int j = i + i;j <= n; j += i)	st[j] = true;
		}
	}
}