L - Prime Number(求n内质数的个数)
2024-08-26 05:45:45
Description
Write a program which reads an integer n and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7.
Input
Input consists of several datasets. Each dataset has an integer n (1 ≤ n ≤ 999,999) in a line.
The number of datasets is less than or equal to 30.
Output
For each dataset, prints the number of prime numbers.
Sample Input
10
3
11
Output for the Sample Input
4
2
5
解题思路:题意很简单,求n内质数的个数,注意n最大也就1e6,既可用埃氏筛也可以用欧拉筛模板,水过!
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
int n,cnt=,prime[maxn];bool isp[maxn];
void euler_sieve(){
memset(isp,true,sizeof(isp));
isp[]=isp[]=false;
for(int i=;i<maxn;++i){
if(isp[i])prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<maxn;++j){
isp[i*prime[j]]=false;
if(i%prime[j]==)break;
}
}
}
int main(){
euler_sieve();
while(~scanf("%d",&n)){
int num=;
for(int i=;prime[i]<=n&&i<cnt;++i)num++;
printf("%d\n",num);
}
return ;
}
最新文章
- ScrollView中嵌套GridView,ListView只显示一行的解决办法
- 如何读懂复杂的C语言声明
- BZOJ 2763 分层图最短路
- 低功耗蓝牙4.0BLE编程-nrf51822开发(3)
- mybatis缓存创建过程
- [React Fundamentals] Introduction to Properties
- java中怎么进行字符串替换?
- c语言字符串翻转系列
- Java使用freemarker导出word和excel
- 朝花夕拾-4-shell
- java的List列表转成Tree(树形)结构列表
- 《深度探索C++对象模型》读书笔记(一)
- 一.javascript核心部分:1.词法结构
- 在docker中部署centos7镜像
- JAVA连接数据库 #03# HikariCP
- nginx反向代理配置相对路径
- echart生成饼状图
- Spring框架简介
- Oracle数据库的语句级读一致性
- 谷歌发布";自动机器学习";技术 AI可自我创造