如何用算法判断一个数是否是猫扑素数

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3419 天前的主题，其中的信息可能已经有所发展或是发生改变。

如果不转换成字符串的话

猫扑素数

形如以 2 开头, 之后跟任意多个 3 的十进制整数而且是个素数, 则它是猫扑素数. 如 2, 23, 233, 2333, 23333 都是猫扑素数, 而 233333 则不是, 它可以分解为 353 x 661.

各位有没有好的思路？

扑素数

素数

十进制

字符串

12 条回复 • 2015-08-20 10:16:07 +08:00

des

2015-08-20 08:01:35 +08:00

我的思路是先 log10 判断位数，再判断（ input -（ input mod 10^n ）） mod 10^n
最后判断是否是素数

statm

2015-08-20 08:09:29 +08:00

不考虑整数上限的话…

https://gist.github.com/statm/9609100e5017b000180f

des

2015-08-20 08:14:59 +08:00

@statm 好吧，还是我算法太弱
另外 chrom 打不开

des

2015-08-20 08:17:14 +08:00

@statm 你忘了判断是否是素数了

statm

2015-08-20 08:18:15 +08:00 via iPhone

@des 这个只检查猫扑数。素数的代码一搜一大堆。

boolean isMopNumber (int i )
{
if (i < 10 ) return i == 2;
else return (i % 10 == 3 ) && isMopNumber (i / 10 );
}

chunk

2015-08-20 09:16:12 +08:00

有意思，顶贴

wangjie

2015-08-20 09:28:46 +08:00

function is 猫扑素数($int ) {
for ($i=0;$<$int;$i+=1 ) {

}
}

wangjie

2015-08-20 09:41:02 +08:00

按空格就发出来了 QAQ 好二啊

aheadlead

2015-08-20 10:02:44 +08:00

@miller-robin

xmbaozi

2015-08-20 10:08:02 +08:00

@statm 只检查猫扑数的话，用正则
/^23+$/.test (23333 )

des

2015-08-20 10:11:10 +08:00 via Android

@xmbaozi 都说了不让转字符串了

zhengnanlee

2015-08-20 10:16:07 +08:00

@aheadlead 太笨了吧用那个算法。。 2333 应该很有规律