首页 > 其他分享 >【模板】素数筛

【模板】素数筛

时间:2024-11-03 14:57:48浏览次数:4  
标签:log 筛法 int 复杂度 vis 素数 模板

模板原题


1. 寻找因数筛法

时间复杂度:\(O(n\sqrt n)\)

核心模板代码如下:

bool isprime(int n)
{
	if (n < 2) return false;	//0和1都不是
	for(int i = 2; i * i <= n; ++ i)
		if(n % i == 0) return false;	//有1和它本身以外的其他因子就不是素数了 
	return true;
}

2. 埃氏筛法

时间复杂度:\(O(n\log \log n)\)

核心模板代码如下:

void Eratosthenes(int n)
{
	vis[0] = vis[1] = true;
	for (int i = 2; i <= n; i++)
	{
		if (!vis[i])
			for (int j = 2 * i; j <= n; j += i)
				vis[j] = true;
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i])
			cout << i << ' ';
	cout << '\n';
}

3. 欧拉筛法

时间复杂度:\(O(n)\)

核心思路:

最小质因数 \(\times\) 最大因数(非自己) \(=\) 这个合数

核心模板代码如下:

void getprimes(int n)
{
	for (int i = 2; i <= n; i ++)
    {
		if (!vis[i]) primes[++ cnt] = i;
        for (int j = 1; primes[j] * i <= n; j ++)
        {
            vis[primes[j] * i] = true;
        	if (i % primes[j] == 0) break;
        }
    }
}

标签:log,筛法,int,复杂度,vis,素数,模板
From: https://www.cnblogs.com/ThySecret/p/18523434

相关文章

  • floyed算法模板
    #include<bits/stdc++.h>#include<vector>usingnamespacestd;intlj[1010][1010];//邻接矩阵//可以换成链式前向星之类的巴拉巴拉,这里用邻接矩阵演示比较清楚intn,m;intflyd[1001][1001];intmain(){ cin>>n>>m; for(inti=1;i<=m;i++){ intu,v,w; cin>>u>>......
  • C++模板元编程 实测
    本文记录在各平台(g++、msvc)中实测《C++模板元编程实战:一个深度学习框架的初步实现》中代码的过程。1.3.2节,作者给出了这一段代码:`templatestructWrapper{templatestructFun_{constexprstaticsize_tvalue=0;};template<>structFun_<int>{constexprst......
  • ElasticSearch7.6.x 模板及滚动索引创建及注意事项
    @目录声明:举例说明创建模板+设置滚动索引+读写判断模板是否存在创建模板应用模板创建索引设置滚动索引添加文档,使用“写”别名查询,使用“读”别名本人先关其他文章链接声明:注意点1:滚动索引是设置索引,而非创建索引,且设置一次结果返回"rolled_over":true,则会按照设定规则创建......
  • 随便写的一点BinTree模板实现
    `#pragmawarning(disable:4996)includeincludeincludeincludetemplatestructBinNode{int_depth;//节点深度int_height;//节点高度T_data;//存储的数据BinNode*_parent;//父节点BinNode*_lChild;//左子节点BinNode*......
  • 判断素数个数
    破天荒的发布c++(^v^)那题是真简单(^v^)1  #include<bits/stdc++.h>2  usingnamespacestd;3  intx,y,jl,a[100001];4  boolssgs(intaa){5    if(a[aa]==0){6      return1;7    }8    return0;9  }10 intma......
  • 常用算法模板
    快速排序defquick_sort(arr):iflen(arr)<=1:#基本情况:如果数组为空或只有一个元素,则返回returnarrelse:pivot=arr[0]#选择基准值(可以选择第一个元素)less_than_pivot=[xforxinarr[1:]ifx<=pivot]#小于等于基准值......
  • 【ChatGPT】让ChatGPT根据固定模板生成报告或文档
    让ChatGPT根据固定模板生成报告或文档在撰写报告或文档时,使用固定模板可以确保内容的统一性和结构的清晰性。利用ChatGPT生成符合特定模板的报告,不仅提高了工作效率,还能确保信息的准确传达。本文将探讨如何设计固定模板并引导ChatGPT生成相应的内容。一、明确报告的目的与......
  • RTX5/FreeRTOS全家桶源码工程综合实战模板集成CANopen组件(2024-10-30)
    【前言】之前的视频教程分享了两期CANopen的专题,配套的例子都是基于裸机的,为了方便大家在OS下使用,本期视频带OS下的支持。CANopen协议栈专题,实战方式系统了解NMT,PDO,SDO,时间戳,同步报文,紧急报文等(2023-10-17)https://www.armbbs.cn/forum.php?mod=viewthread&tid=121438CANopen......
  • 洛谷题单指南-字符串-P3369 【模板】普通平衡树
    原题链接:https://www.luogu.com.cn/problem/P3369题意解读:平衡树的基本操作,模版题。解题思路:1、二叉搜索树-BST二叉搜索树满足这样的性质:每一个节点的权值大于它的左儿子,小于它的右儿子。对BST进行中序遍历,将得到一个从小到大的有序序列,因此BST是为了维护一个有序序列的动态......
  • 模板初阶及STL简介
    目录一.模板初阶1.泛型函数2.函数模板1.函数模板概念2.函数模板使用格式3.函数模板的原理4.函数模板的实例化5.模板参数的匹配原则3.类模板1.类模板的定义格式2.类模板的实例化二.STL简介1.什么是STL2.STL的版本3.STL的六大组件4.如何学习STL5.STL的缺陷......