素数定理:

素数有无穷多个,能估计出一个小于正实数x的素数有多少个,并用π(x)来表示,这就是素数定理

定理内容: 随着x的增长,π(x)/(x/lnx)=1 

具体数据见下表:

n            1e3       1e4       1e5       1e6        1e7

π(n)       168       1229     9892     78498   664579

n/ln n     145       1086     8686     72382   620421


求1~10的n次方素数个数的位数:

利用素数定理,用n/ln n的位数代替.根据位数公式 ln(n/ln n)+1就是该问题的解

int get_prime_nums(int n){  //返回1 ~ 10^n素数个数的位数
   double m=double(n-log10(n)-log10(log(10)));
   return int(m)+1;
}


Logo

助力广东及东莞地区开发者,代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展,成为松山湖开发者首选的工作与学习平台

更多推荐