阶乘和素数个数
用$pi(n)$表示不大于n的素数个数.比如,$pi(13)$=6. (不大于13的素数有:2,3,5,7,11,13)
13有一个很有意思的性质:$pi(13)$=6=1!*3!,即:$pi(13)$等于13的数字组成(1,3)的阶乘的乘积.
若自然数n满足:$pi(n)$等于n的数字组成的阶乘的乘积,我们就称n为PF数.(^_^,实在不知道取什么名字了).
有同样性质的数还有1512,1520,1521等等.
更难得的,$pi(226130351)$=2!*2!*6!*1!*3!*0!*3!*5!*1!,并且,226130351是素数.
如果n既是PF数,又是素数,则称n为PFP数.
问题:
1):求出10^18内的所有PF数.
2): 13,226130351是前2个PFP数,请求出接下来的两个PFP数. 这么难得的数字是怎么给想到的? 呵呵,见A066457。
我估计如果解决问题1),应该有可能再得到一个PFP数。 10^18, 太难了吧,不知什么时候可以算出来。 呵呵,注意到,数字组成的阶乘的乘积是与顺序无关的。
因此,$10^18$内的的数的数字组成的阶乘的乘积的形式一共只有:$C_27^9$=4686825个。
呵呵,现在关键是计算$pi(n)$。
问题是
$pi(n), n <= 10^18$
的数据是不完整的!!
而计算$pi(n)$在n很大时是比较慢的
想起来了, 某人给我一段Haskell代码
可以算$pi(n)$
可惜啊
似乎大概被我丢弃了 对PFP数来说,在$10^18$内,仅有2829个素数是候选的PFP数,它们的序号在下面的prime_index.rar 中。最大的候选PFP数可能是第30091839012864000个素数。(如果第30091839012864000个素数小于$10^18$) 你还是想办法把
$O(n^{2/3})$
的$pi(n)$算法
先做好了吧 呵呵,这个题还是可以算到10^14的。
不知道哪位装了mathematical,mathematical里有个函数PrimePi(n)是计算n内的素数个数的,据说可以算到8*10^13。因此,计算到10^14还是没有问题的。
页:
[1]