一道数学编程题：有兴趣的来试试

pacelife · 发表于 2015-11-12 22:19:41

我们称197为一个循环质数，因为它的所有轮转形式: 197, 971和719都是质数。
100以下有13个这样的质数: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97.
100万以下有多少个循环质数？
能否更进一步，算出这些循环质数分别为多少？

fwsc · 发表于 2015-11-12 23:29:02

是需要所有轮转形式都为质数么？

也就是说判断一个质数是否为循环质数时，组成的数字里面不能有2、4、6、8、0？

pacelife · 发表于 2015-11-13 06:30:58

fwsc 发表于 2015-11-12 23:29
- D" N K" D6 X! q8 I是需要所有轮转形式都为质数么？
; H7 K% d& M- ~* ^7 W4 d8 C
' }8 ~7 \+ Y: `# T- G* a; N6 I也就是说判断一个质数是否为循环质数时，组成的数字里面不能有2、4、6、 ...

说的对，但是这个只是必要条件而已，按照它筛选出来的数还是非常多，事实上，符合条件的就几十个而已

阳光小院暖茶 · 发表于 2015-11-13 09:37:29

179,197,719,791,917,971, 不是6个这样的数么？你这个轮转的定义是什么？

pacelife · 发表于 2015-11-13 10:14:48

阳光小院暖茶发表于 2015-11-13 09:37 : v! _, c" `# M% u9 ]$ s
179,197,719,791,917,971, 不是6个这样的数么？你这个轮转的定义是什么？

主贴例子已经很清楚了，比如123这个数，它的轮转数是123,231,312,比如17的轮转数是17,71，5的轮转数就他本身一个

阳光小院暖茶 · 发表于 2015-11-13 10:17:58

这样行不？假设要得出一百万以内的所有轮转形式为素数的素数，
第一步，得到一张一百万以内的素数表；
第二步，大于一位的素数，如果它含有0,2,4,6,8,5,就把它剔除，得到一张更精简的一百万以内的素数表；
第三步，逐一检查第二张素数表的素数，看它的所有轮转形式是否为素数
哈哈，这个思路太简单了

阳光小院暖茶 · 发表于 2015-11-13 13:19:59

你的这个剔除没必要，因为数字之和能被3整除的话，它就不会出现在第一张素数表中了。一百万以内的素数有78,498个(百度)，轮转素数条件挺苛刻的，我猜不超过500个。但是具体怎么编程我不会，有难度，你要是做出来了的话，把结果贴出来欣赏欣赏哈。

pacelife · 发表于 2015-11-13 14:13:12

阳光小院暖茶发表于 2015-11-13 13:19 $ \: i( r2 Q& j: y
你的这个剔除没必要，因为数字之和能被3整除的话，它就不会出现在第一张素数表中了。一百万以内的素数有78, ...

我早就做出来了，一共55个，代码今天回去分享给你

pacelife · 发表于 2015-11-13 20:43:09

本帖最后由 pacelife 于 2015-11-13 20:57 编辑

阳光小院暖茶发表于 2015-11-13 13:19 / c$ y7 i# @, z, _3 ^/ G# B& r
你的这个剔除没必要，因为数字之和能被3整除的话，它就不会出现在第一张素数表中了。一百万以内的素数有78, ...

我用两种方法算出来了，第一种是暴力计算法，费时5.39秒之多，另外一种就是你提出的多重筛选法，仅耗时0.078秒，可见适当的筛选对计算量的影响是巨大的

阳光小院暖茶 · 发表于 2015-11-16 14:16:09

你这个语言好像不是c语言吧？是什么语言啊？能编程判断一个整数是否为素数吗？一个很大的整数，如果人力判断它是不是素数，很难啊

		自动登录	找回密码
密码			注册会员

一道数学编程题：有兴趣的来试试

相关帖子

点评

评分

点评

点评

本帖子中包含更多资源