素数&欧拉函数
2024-10-09 02:55:41
素数表
const int maxN
找[1,maxN)内的素数
int prime[int I]
第I个素数
const int maxN=1e5+5;
int prime[maxN];
bool mark[maxN];
void init_prime()
{
int cnt=0;
for(int i=2;i<maxN;++i)
{
if(!mark[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&prime[j]*i<maxN;++j)
{
mark[prime[j]*i]=true;
if(i%prime[j]==0)break;
}
}
}
欧拉函数表(同时得到素数表)
const int maxn
同上
int prime[int j]
同上
int phi[int j]
欧拉函数
const int maxN=1e5+5;
int prime[maxN],phi[maxN];
bool mark[maxN];
void init_prime_phi()
{
phi[1]=1;
int cnt=0;
for(int i=2;i<maxN;++i)
{
if(!mark[i]){prime[++cnt]=i;phi[i]=i-1;}
for(int j=1;j<=cnt&&prime[j]*i<maxN;++j)
{
mark[prime[j]*i]=true;
if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
最新文章
- Texstudio中文乱码问题
- Http协议与TCP协议简单理解(转)
- [转]UpdatePanel的用法详解
- Productivity Power Tools 的使用
- codevs 1203 判断浮点数是否相等
- [Vue]学习中遇到的疑点
- UVa 122 (二叉树的层次遍历) Trees on the level
- Oracle 一次 锁表 处理小记
- HDU 2037 今年暑假不AC (贪心)
- 理解sparse coding
- Android WiFi管理(WIFI_SERVICE)
- 头文件limits—各个类型的数据的范围
- Android总结篇系列:Activity启动模式(lauchMode)
- 由asp的一个错误,看语言的不同:asp &; java
- Apache URL重写的配置 及其 apache500错误
- linux服务器---安装samba
- 在Asp.net Core中使用中间件来管理websocket
- 版本控制工具(下)——Git的远程仓库、分支管理与其它操作
- 分布式服务框架dubbo入门实例
- Raspberry Pi 3b+ 配置摄像头
热门文章
- 携程首页--使用flex布局实现
- C++ 同类不同对象的互相访问
- 【memcache】Memcached
- mysql中的PACK_KEYS
- Date 对象-->;概念、创建以及方法
- "段落"组件:<;p>; —— 快应用组件库H-UI
- Pytest系列(20)- allure结合pytest,allure.step()、allure.attach的详细使用
- AJ学IOS(25)UI之触摸事件
- 前端笔记(关于css盒模型知识整理)
- Docker常用命令--ps/attach/run