# 素数个数的位数 |
||
|
||
# description | ||
|
||
# input | ||
|
||
# output | ||
|
||
# sample_input | ||
|
||
# sample_output | ||
|
||
# hint | ||
|
数论问题,应用素数定理第一个估计即可轻松破之~~
素数定理:
对正实数x,定义π(x)为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。
- ![pi(x)approxfrac{x}{ln,x}](http://upload.wikimedia.org/math/4/9/7/497ec682ef0aee17abc7272819028a83.png)
其中ln x为x的自然对数。上式的意思是当x趋近∞,π(x)与x/ln x的比值趋近1。但这不表示它们的数值随着x增大而接近。
下面是对π(x)更好的估计:
- ![pi(x)={rm Li} (x) + O left(x e^{-frac{1}{15}sqrt{ln,x}}right)](http://upload.wikimedia.org/math/d/5/b/d5b07a01ea1c56a87992eb67ed977dfd.png),当x 趋近∞。
其中(对数积分),而关系式右边第二项是误差估计,详见大O符号。
下表比较了π(x),x/ln x和Li(x):
-
*x* π(*x*)[1] π(*x*) − *x* / ln *x*[2] π(*x*) / (*x* / ln *x*) li(*x*) − π(*x*)[3] *x* / π(*x*) 10 4 −0.3 0.921 2.2 2.500 102 25 3.3 1.151 5.1 4.000 103 168 23 1.161 10 5.952 104 1,229 143 1.132 17 8.137 105 9,592 906 1.104 38 10.425 106 78,498 6,116 1.084 130 12.740 107 664,579 44,158 1.071 339 15.047 108 5,761,455 332,774 1.061 754 17.357 109 50,847,534 2,592,592 1.054 1,701 19.667 1010 455,052,511 20,758,029 1.048 3,104 21.975 1011 4,118,054,813 169,923,159 1.043 11,588 24.283 1012 37,607,912,018 1,416,705,193 1.039 38,263 26.590 1013 346,065,536,839 11,992,858,452 1.034 108,971 28.896 1014 3,204,941,750,802 102,838,308,636 1.033 314,890 31.202 1015 29,844,570,422,669 891,604,962,452 1.031 1,052,619 33.507 1016 279,238,341,033,925 7,804,289,844,393 1.029 3,214,632 35.812 1017 2,623,557,157,654,233 68,883,734,693,281 1.027 7,956,589 38.116 1018 24,739,954,287,740,860 612,483,070,893,536 1.025 21,949,555 40.420 1019 234,057,667,276,344,607 5,481,624,169,369,960 1.024 99,877,775 42.725 1020 2,220,819,602,560,918,840 49,347,193,044,659,701 1.023 222,744,644 45.028 1021 21,127,269,486,018,731,928 446,579,871,578,168,707 1.022 597,394,254 47.332 1022 201,467,286,689,315,906,290 4,060,704,006,019,620,994 1.021 1,932,355,208 49.636 1023 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309 1.020 7,250,186,216 51.939
素数定理可以给出第n个素数p(n)的渐近估计:
- ![p(n)sim nln,n.](http://upload.wikimedia.org/math/b/7/c/b7c223a92d307c0d279bda8784a6c4a8.png)
它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个,它是素数的概率大约是1/ln n。
下面是我AC的代码
[C++]
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5
6 using namespace std;
7
8 int main()
9 {
10 long long n;
11
12 while(cin>>n)
13 {
14 long long t=n;
15 char s[20];
16 t*=log(10);
17 sprintf(s,"%lld",t);
18 cout<<n-strlen(s)+1<<endl;
19 }
20
21 return 0;
22 }
原文链接: https://www.cnblogs.com/lzj-0218/archive/2013/05/04/3059681.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/87140
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!