检验素数的方法（c语言）我来我网·5come5 Forum

本页主题: 检验素数的方法（c语言）	显示签名 \| 打印 \| 加为IE收藏 \| 收藏主题 \| 上一主题 \| 下一主题

硬度为7

∷ 性别:

∷ 状态:

∷ 头衔: 禁你妈B的IP，傻B儿~~~

∷ 等级: 人见人爱

∷ 家族: 水族馆

∷ 发贴: 2572

∷ 威望: 0

∷ 浮云: 982

∷ 在线等级:

∷ 注册时间: 2006-10-27

∷ 最后登陆: 2024-08-31

【复制此帖地址只看此人回复】

5come5帮你背单词 [ clap /klæp/ vt. 拍手；vi. 拍击；n. 拍手，鼓掌，霹雳声，破裂声 ]

检验素数的方法（c语言）

看到课本上讲了，有三个方法，一个是一个一个连续的加，原理很简单，一个是循环到所要验证数的1/2，一个是验证到待验证数的平方根。
后两个搞不明白原理，是不是我数学学的矬...
期待大家详细的解答...

Posted: 2007-04-28 16:28 | [楼主]

zc1984

∷ 性别:

∷ 状态:

∷ 头衔: 上帝模式

∷ 等级: 荣誉会员

∷ 家族: 战略研究所

∷ 发贴: 10096

∷ 威望: 5

∷ 浮云: 0

∷ 在线等级:

∷ 注册时间: 2004-08-24

∷ 最后登陆: 2017-06-08

【复制此帖地址只看此人回复】

5come5帮你背单词 [ greece /gri:s/ n. 希腊 ]

你说的那种是筛子哈~~

Posted: 2007-04-28 17:45 | [1 楼]

硬度为7

∷ 性别:

∷ 状态:

∷ 头衔: 禁你妈B的IP，傻B儿~~~

∷ 等级: 人见人爱

∷ 家族: 水族馆

∷ 发贴: 2572

∷ 威望: 0

∷ 浮云: 982

∷ 在线等级:

∷ 注册时间: 2006-10-27

∷ 最后登陆: 2024-08-31

【复制此帖地址只看此人回复】

5come5帮你背单词 [ overthrow /,əuvə'θrəu/ n. 推翻，打倒；vt. 推翻，打倒 ]

期待楼上强人详解...我就想弄明白它的数学原理...

Posted: 2007-04-28 20:20 | [2 楼]

jiju84

∷ 性别:

∷ 状态:

∷ 头衔: 【做人要低调！！】

∷ 等级: 前途无量

∷ 家族: J&S

∷ 发贴: 6455

∷ 威望: 0

∷ 浮云: 1253

∷ 在线等级:

∷ 注册时间: 2005-03-07

∷ 最后登陆: 2010-03-18

【复制此帖地址只看此人回复】

5come5帮你背单词 [ attract /ə'trækt/ vt. 吸引，引诱 ]

一个是验证到待验证数的平方根

这个是比较好的

Posted: 2007-04-28 20:49 | [3 楼]

硬度为7

∷ 性别:

∷ 状态:

∷ 头衔: 禁你妈B的IP，傻B儿~~~

∷ 等级: 人见人爱

∷ 家族: 水族馆

∷ 发贴: 2572

∷ 威望: 0

∷ 浮云: 982

∷ 在线等级:

∷ 注册时间: 2006-10-27

∷ 最后登陆: 2024-08-31

【复制此帖地址只看此人回复】

5come5帮你背单词 [ could /kud, kəd/ aux. & v. 可以，能 ]

Quote:

引用第3楼jiju84于2007-04-28 20:49发表的:
一个是验证到待验证数的平方根

这个是比较好的

我想知道数学原理...

Posted: 2007-04-28 20:56 | [4 楼]

zbp

∷ 性别: 保密 ∷ 状态: 该用户目前不在线

∷ 头衔: 三好学生

∷ 等级: 人见人爱

∷ 家族: 起早不摸黑

∷ 发贴: 2892

∷ 威望: 0

∷ 浮云: 1172

∷ 在线等级:

∷ 注册时间: 2005-03-19

∷ 最后登陆: 2007-04-30

【复制此帖地址只看此人回复】

5come5帮你背单词 [ carpet /'ka:pit/ n. 地毯 ]

假设给定的一个数N不是素数,X是一个大于N(0.5)的因子,那么N可以表示为
N = X * Y;
由题设X > N(0.5)
Y 必然小于N(0.5)
按照从小到大的筛选顺序则Y会先被筛选到从而判断N为非素数

因此最多检测到该数的平方根就可以了

Posted: 2007-04-29 12:11 | [5 楼]

依然随意

∷ 性别:

∷ 状态:

∷ 等级: 前途无量

∷ 家族: ⊙JAY菊爱园⊙

∷ 发贴: 5922

∷ 威望: 0

∷ 浮云: 760

∷ 在线等级:

∷ 注册时间: 2006-09-25

∷ 最后登陆: 2022-10-30

【复制此帖地址只看此人回复】

5come5帮你背单词 [ queue /kju:/ v. 长队，排队 n. 队，列；vt. 排队 ]

任意一个素数X的所有公因子只有1和X本身。
所以对任意一个非素数S，有 S=P*Q成立，（P,Q为正整数）
应为 S=根号S*根号S,观察可知，
P<=根号S||Q<=根号S成立。
综上所述：如果S是一个非素数，则一定有小于根号S的因子。
逆否命题：如果S没有小于根号S的因子，则S是一个素数。。
完毕。

Posted: 2007-04-29 16:49 | [6 楼]

haifan

∷ 性别:

∷ 状态:

∷ 等级: 栋梁之材

∷ 发贴: 897

∷ 威望: 0

∷ 浮云: 1122

∷ 在线等级:

∷ 注册时间: 2006-09-07

∷ 最后登陆: 2009-10-22

【复制此帖地址只看此人回复】

5come5帮你背单词 [ heir //ə/ n. 继承人 ]

这个好想的嘛，假设不是素数，就象15，3×5是，那就没有必要循环到5了嘛。到一半或者平方根的时候就行了。如果是的话就已经判断出来了，没有必要循环到整个这个数

Posted: 2007-04-29 17:07 | [7 楼]

lkk

∷ 性别:

∷ 状态:

∷ 头衔: 做神一样的男人

∷ 等级: 人见人爱

∷ 发贴: 3954

∷ 威望: 0

∷ 浮云: 1248

∷ 在线等级:

∷ 注册时间: 2005-09-30

∷ 最后登陆: 2012-01-14

【复制此帖地址只看此人回复】

5come5帮你背单词 [ nominate /'nomineit/ v. 提名 ]

一个数n如果不是素数,那么它必有除1以外的小于根号n的因数...
感觉这很好理解啊

Posted: 2007-04-30 21:30 | [8 楼]

lkk

∷ 性别:

∷ 状态:

∷ 头衔: 做神一样的男人

∷ 等级: 人见人爱

∷ 发贴: 3954

∷ 威望: 0

∷ 浮云: 1248

∷ 在线等级:

∷ 注册时间: 2005-09-30

∷ 最后登陆: 2012-01-14

【复制此帖地址只看此人回复】

5come5帮你背单词 [ reason /'ri:zn/ n.原因，理性，判断力，理智；vt. 论证，与…评理，劝说；vi. 推理，思考，评理 ]

好像有一个类似的定理叫做:
一个正合数(非素数)的除1以外的最小正因数一定是素数

这个可以用反正法证明

Posted: 2007-04-30 21:34 | [9 楼]

5come5帮你背单词 [ clap /klæp/ vt. 拍手；vi. 拍击；n. 拍手，鼓掌，霹雳声，破裂声 ] 检验素数的方法（c语言）

5come5帮你背单词 [ greece /gri:s/ n. 希腊 ]

5come5帮你背单词 [ overthrow /,əuvə'θrəu/ n. 推翻，打倒；vt. 推翻，打倒 ]

5come5帮你背单词 [ attract /ə'trækt/ vt. 吸引，引诱 ]

5come5帮你背单词 [ could /kud, kəd/ aux. & v. 可以，能 ]

Quote:

5come5帮你背单词 [ carpet /'ka:pit/ n. 地毯 ]

5come5帮你背单词 [ queue /kju:/ v. 长队，排队 n. 队，列；vt. 排队 ]

5come5帮你背单词 [ heir //ə/ n. 继承人 ]

5come5帮你背单词 [ nominate /'nomineit/ v. 提名 ]

5come5帮你背单词 [ reason /'ri:zn/ n.原因，理性，判断力，理智；vt. 论证，与…评理，劝说；vi. 推理，思考，评理 ]

5come5帮你背单词 [ clap /klæp/ vt. 拍手；vi. 拍击；n. 拍手，鼓掌，霹雳声，破裂声 ]

检验素数的方法（c语言）