机械必威体育网址

 找回密码
 注册会员

QQ登录

只需一步,快速开始

搜索
查看: 4611|回复: 11
打印 上一主题 下一主题

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

[复制链接]
跳转到指定楼层
1#
发表于 2015-11-12 22:19:41 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
我们称197为一个循环质数,因为它的所有轮转形式: 197, 971和719都是质数。
" k/ F' ?2 |1 i100以下有13个这样的质数: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 和97.
/ e/ ?& D7 L) H2 o- `0 \100万以下有多少个循环质数?; W* U8 r& u, n# J* S. ]
能否更进一步,算出这些循环质数分别为多少?
" V  V0 W( ~% q
( F2 t& o& \& @5 [! `5 N1 k+ V% \. |7 l: O/ V1 Y# M) P$ {- K
回复

使用道具 举报

2#
发表于 2015-11-12 23:29:02 | 只看该作者
是需要所有轮转形式都为质数么?
. g& F% I% A0 K1 V5 D$ w# B" T  P% N+ ]
也就是说判断一个质数是否为循环质数时,组成的数字里面不能有2、4、6、8、0?
) e# e9 y# Z; ]* ]

点评

大于1位数不能有5  发表于 2015-11-13 00:09

评分

参与人数 1威望 +1 收起 理由
冷水黄金 + 1 思想深刻,见多识广!

查看全部评分

回复 支持 反对

使用道具 举报

3#
 楼主| 发表于 2015-11-13 06:30:58 | 只看该作者
fwsc 发表于 2015-11-12 23:29
3 {# Q3 n) q2 u& ?是需要所有轮转形式都为质数么?
" I( f9 r1 J9 A5 }& l. m$ H2 ?
9 ~1 d: P( h6 ~1 u/ S也就是说判断一个质数是否为循环质数时,组成的数字里面不能有2、4、6、 ...
7 R$ B7 y6 n  I; @) e
说的对,但是这个只是必要条件而已,按照它筛选出来的数还是非常多,事实上,符合条件的就几十个而已  b, e: V" L  s) k. ^* z% U1 t
回复 支持 反对

使用道具 举报

4#
发表于 2015-11-13 09:37:29 | 只看该作者
179,197,719,791,917,971, 不是6个这样的数么?你这个轮转的定义是什么?

点评

这个轮转的意思不是所有数的组合排列,而是有一定顺序的  发表于 2015-11-13 10:16
这个轮转的意思不是所有数的组合排列,而是有一定顺序的  发表于 2015-11-13 10:16
回复 支持 反对

使用道具 举报

5#
 楼主| 发表于 2015-11-13 10:14:48 | 只看该作者
阳光小院暖茶 发表于 2015-11-13 09:37 ! |" D- m6 D* M7 x2 k; j
179,197,719,791,917,971, 不是6个这样的数么?你这个轮转的定义是什么?

& T. }: g9 V. J主贴例子已经很清楚了,比如123这个数,它的轮转数是123,231,312,比如17的轮转数是17,71,5的轮转数就他本身一个8 C& z) I( n0 w0 r
( H" b, b" l* m/ v; s! s! l6 a1 v
回复 支持 反对

使用道具 举报

6#
发表于 2015-11-13 10:17:58 | 只看该作者
这样行不?假设要得出一百万以内的所有轮转形式为素数的素数,; Z7 j3 E  H* b2 U0 a: [8 }
第一步,得到一张一百万以内的素数表;$ N9 S3 B4 ^$ O# n
第二步,大于一位的素数,如果它含有0,2,4,6,8,5,就把它剔除,得到一张更精简的一百万以内的素数表;
+ x) r8 j9 z$ p" }1 A4 O第三步,逐一检查第二张素数表的素数,看它的所有轮转形式是否为素数8 w3 F, Z" E: m' X  M) u& d
哈哈,这个思路太简单了

点评

晚上我回去把你的思路做成程序,应该是可以秒出结果的  发表于 2015-11-13 12:51
晚上我回去把你的思路做成程序,应该是可以秒出结果的  发表于 2015-11-13 12:51
晚上我回去把你的思路做成程序,应该是可以秒出结果的  发表于 2015-11-13 12:50
这个思路完全可行,而且计算量也相当少,很不错,另外其实可以把所有数子加起来可以被3整除的也一起剔除,这样计算量会更少  发表于 2015-11-13 12:49
回复 支持 反对

使用道具 举报

7#
发表于 2015-11-13 13:19:59 | 只看该作者
你的这个剔除没必要,因为数字之和能被3整除的话,它就不会出现在第一张素数表中了。一百万以内的素数有78,498个(百度),轮转素数条件挺苛刻的,我猜不超过500个。但是具体怎么编程我不会,有难度,你要是做出来了的话,把结果贴出来欣赏欣赏哈。
回复 支持 反对

使用道具 举报

8#
 楼主| 发表于 2015-11-13 14:13:12 | 只看该作者
阳光小院暖茶 发表于 2015-11-13 13:19
. D9 g! I/ ?( B; q! {你的这个剔除没必要,因为数字之和能被3整除的话,它就不会出现在第一张素数表中了。一百万以内的素数有78, ...

2 g; @" A# T9 S! v6 R我早就做出来了,一共55个,代码今天回去分享给你' L; p6 Z; M3 U2 D5 i
回复 支持 反对

使用道具 举报

9#
 楼主| 发表于 2015-11-13 20:43:09 | 只看该作者
本帖最后由 pacelife 于 2015-11-13 20:57 编辑 # V7 S! C, O5 c# e, z; _% \" e2 d& c
阳光小院暖茶 发表于 2015-11-13 13:19
/ Y: i7 w) g- X5 K! b你的这个剔除没必要,因为数字之和能被3整除的话,它就不会出现在第一张素数表中了。一百万以内的素数有78, ...

* N( }8 u! V$ n0 H$ o我用两种方法算出来了,第一种是暴力计算法,费时5.39秒之多,另外一种就是你提出的多重筛选法,仅耗时0.078秒,可见适当的筛选对计算量的影响是巨大的- ?+ D  c/ g/ J- J) z

) M) ^+ q- }" S7 Z; G
6 t4 b3 F+ X# z8 `  C) A/ k
3 l/ k; o2 `2 I9 ?2 q+ A% q- C: u1 N# S& y* _" K0 _

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册会员

x
回复 支持 反对

使用道具 举报

10#
发表于 2015-11-16 14:16:09 | 只看该作者
你这个语言好像不是c语言吧?是什么语言啊?能编程判断一个整数是否为素数吗?一个很大的整数,如果人力判断它是不是素数,很难啊
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

小黑屋|手机版|Archiver|机械必威体育网址 ( 京ICP备10217105号-1,京ICP证050210号,浙公网安备33038202004372号 )

GMT+8, 2024-11-13 20:27 , Processed in 0.056724 second(s), 20 queries , Gzip On.

Powered by Discuz! X3.4 Licensed

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表