阶乘和素数个数

medie2005

用$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数.

gxqcn

这么难得的数字是怎么给想到的？

medie2005

呵呵，见A066457。 我估计如果解决问题1），应该有可能再得到一个PFP数。

liangbch

10^18， 太难了吧，不知什么时候可以算出来。

medie2005

呵呵，注意到，数字组成的阶乘的乘积是与顺序无关的。 因此，$10^18$内的的数的数字组成的阶乘的乘积的形式一共只有：$C_27^9$=4686825个。 呵呵，现在关键是计算$pi(n)$。

无心人

问题是 $pi(n), n <= 10^18$ 的数据是不完整的！！ 而计算$pi(n)$在n很大时是比较慢的

无心人

想起来了， 某人给我一段Haskell代码 可以算$pi(n)$ 可惜啊 似乎大概被我丢弃了

medie2005

对PFP数来说，在$10^18$内，仅有2829个素数是候选的PFP数，它们的序号在下面的prime_index.rar 中。最大的候选PFP数可能是第30091839012864000个素数。（如果第30091839012864000个素数小于$10^18$）

无心人

你还是想办法把 $O(n^{2/3})$ 的$pi(n)$算法 先做好了吧

medie2005

呵呵，这个题还是可以算到10^14的。 不知道哪位装了mathematical,mathematical里有个函数PrimePi(n)是计算n内的素数个数的，据说可以算到8*10^13。因此，计算到10^14还是没有问题的。