当前位置:网站首页>埃氏筛选法:统计素数个数
埃氏筛选法:统计素数个数
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本身为倍数进行递增,提高效率。
边栏推荐
猜你喜欢
windos安装Mysql8.0,及解决重新登录异常问题 ERROR 1045 (28000)
10个 Istio 流量管理 最常用的例子,你知道几个?
Puyuan Jingdian turned losses into profits in the first half of the year, and high-end products continued to develop!Are you optimistic about "Huawei" in the instrument industry?
SQLi-LABS Page-2 (Adv Injections)
Ali Ermi: Without accept, can a TCP connection be established?
Excel如何打出正负号?Excel打出正负号的方法
Lyapp exponents and bifurcation diagrams for fractional chaotic systems
同步锁synchronized追本溯源
[corctf 2022] section
Cholesterol-PEG-Thiol, CLS-PEG-SH, Cholesterol-PEG-Sulfhydryl for improved solubility
随机推荐
微软Excel表格点击单元格行和列都显示颜色怎么弄?聚光灯效果设置
浅谈Numpy中的shape、reshape函数的区别
Word第一页不要页眉怎么设置?设置Word首页不要页眉方法教程
同步锁synchronized追本溯源
windos安装Mysql8.0,及解决重新登录异常问题 ERROR 1045 (28000)
Endpoint mode for NetCore routing
Word第一页空白页怎么删除?删除Word第一页空白页方法教程
自监督学习 —— MoCo v2
SecureCRT 设置超时自动断开连接时长
Characteristics and Development Prospects of Korea's Cyber Security System
安科瑞支持以太网通讯、profibus通讯嵌入式电能表APM指导性技术要求-Susie 周
LED闪烁 闪灯芯片IC 手电筒IC 闪灯控制IC 闪烁IC流水灯
【Efficient Tools】Remote Control Software ToDesk (Favorites)
PHP 二维数组根据某个字段排序
CMake installation upgrade higher version
MySQL慢查询的多个原因
mysql多表左链接查询
小黑leetcode清爽雨天之旅,刚吃完宇飞牛肉面、麻辣烫和啤酒:112. 路径总和
fixed investment fund
什么是源文件?