【NEFU 117 素数个数的位数】(素数定理)
2024-08-30 06:47:54
Description
小明是一个聪明的孩子,对数论有着很浓烈的兴趣。
他发现求1到正整数10n 之间有多少个素数是一个很难的问题,该问题的难以决定于n 值的大小。
现在的问题是,告诉你n的值,让你帮助小明计算小于10n的素数的个数值共有多少位?
Input
输入数据有若干组,每组数据包含1个整数n(1 < n < 1000000000),若遇到EOF则处理结束。
Output
对应每组数据,将小于10n 的素数的个数值的位数在一行内输出,格式见样本输出。同组数据的输出,其每个尾数之间空一格,行末没有空格。
Sample Input
3
7
Sample Output
3
6
Hint
素数定理
题解
素数定理:\(\pi(x)\):小于x的素数个数
\(\pi(x)/(x/lnx)=1\),这个公式随着x的增长而愈发准确。
10进制的位数公式为\(lgx+1\)
\[\begin {aligned}
Ans&=lg\frac{10^n}{ln^{(10^n)}} +1\\\
&=lg^{10^n}-lg^{ln^{10^n}} +1\\\
&= n-lg^{nln^{10}}+1\\\
&=n-(lg^n+lg^{ln^{10}})+1\\\
&=n-lg^n-lg^{ln^{10}}+1
\end {aligned}
\]
Ans&=lg\frac{10^n}{ln^{(10^n)}} +1\\\
&=lg^{10^n}-lg^{ln^{10^n}} +1\\\
&= n-lg^{nln^{10}}+1\\\
&=n-(lg^n+lg^{ln^{10}})+1\\\
&=n-lg^n-lg^{ln^{10}}+1
\end {aligned}
\]
参考代码
#include<cmath>
#include<iostream>
using namespace std;
int main(){
int n;
while(cin>>n){
int m=double(n-log10(n)-log10(log(n)));
cout<<int(m)+1<<endl;
}
return 0;
}
最新文章
- Windows Azure 服务总线和物联网
- Google Gson 使用简介
- 老毛桃u盘装系统制作工具
- Android中实现如下多语言选择Radiobutton效果
- Echarts-画叠加柱状图,双折线图
- Linux_JDK安装
- Swift使用FMDB操作SQLite
- 深入浅出MySQL双向复制技术
- Linux inotify功能及实现原理
- C#发送Email邮件(实例:QQ邮箱和Gmail邮箱)
- Amoeba相关产品及其介绍
- 【BZOJ】1070: [SCOI2007]修车
- AppDelegate关于应用程序挂起、复原与终止的代理方法
- EasyUI - 后台管理系统 - 增加,删除,修改
- iOS 之 绘图简介
- gstunnel---一个网络安全管道
- MQTT客户端库-Paho GO
- 发现一个非常有趣好用的git博主,收录热门OC、swift项目三方架构
- 1259 整数划分 V2
- Java的Fork/Join任务
热门文章
- 手把手教你如何在Fire fox火狐浏览器里在线识别下载视频(超强大)(博主推荐)
- spring boot eureka client
- sybase修改默认字符集为cp936
- Random Query CodeForces - 846F
- 题解报告:poj 2631 Roads in the North(最长链)
- synchronized(6)修饰语方法之:static方法
- SPRING-BOOT系列之SpringBoot的诞生及其和微服务的关系
- 三色灯渐变DIY制作
- 动手实现 React-redux(一):初始化工程
- CCF|最大波动|Java|100