数学建模社区-数学中国
标题:
判断一个数是否为素数（自编的）
[打印本页]
作者:
小草远在天涯
时间:
2010-11-8 18:17
标题:
判断一个数是否为素数（自编的）
本帖最后由 小草远在天涯 于 2010-11-8 18:48 编辑
. m; y) y3 P& e# y3 s R
- M7 D! v% ]3 {, O
#include "stdio.h"
o1 E" W% v6 X' ?7 ]" \# A
main()
' H; A$ k' X$ o- i& P3 ~
{
) t' J! X- Y7 m+ G. N9 p& i/ d
int m,i,x;
g- B) N" N% ?. ~: t; U* H8 z [% }
x=0;
: T; d& Y0 S9 |9 W4 P; `7 f
scanf("%d",&m);
; ~+ J' ~7 ~( Z0 W# L4 u8 H, `
for(i=1;i<=m;i++)
+ h# _" u8 R7 M' K, f0 D
{
6 e0 b6 o6 k$ I
if(m%i==0)
* a( {( [ }9 P O" J
x+=1;
- t4 q4 l( ?$ f* U
}
) Z% Y' s& |3 D& r5 c, q
if(x>2)
( L2 \! @6 V4 U( l$ a
printf("该数不是素数！");
' }/ h. D. K8 F6 z/ u
else
, i+ x$ t! U5 n i# r p8 u
printf("该数是素数！");
* Y3 {7 L2 h2 \0 O* W
}
9 e- j N% @6 V
思路：素数就是除了1和它本身之外不能被除的整数。也就是说素数只能被两个数相除，一个是1，另一个是它本身。那就简单了，只要判断是否有1和它本身之外的数，就行了。
8 s' W+ K( U. c& f
教材上在搞什么啊！我到现在还是不明白，真是看不懂！
7 ]$ [; Q. [7 m" t
我教材的程序是这样的。
P5 D) e7 {4 Y2 A f7 h
#include "stdio.h"
% M* `* I* l1 I8 b: M
#include "math.h"
& }% J# k7 T: C4 R/ N
main()
( z1 A3 j. w" [- v
{
3 R3 r! p- K* A, y3 H
int m,i,x;
, n+ Z7 O* `+ b/ Z0 g# V& H J: j' s
scanf("%d",&m);
% _' ?# O9 s7 |: t5 w' P
x=sqrt(m);
) [9 x$ d. i: y+ Q
for(i=2;i<=x;i++)
- S" _" Y% i/ s1 Y5 t% g
if(m%i==0)break;
. H1 c; h4 J0 |1 E4 V
if(i>x)printf("%d是素数",m);
1 S9 o" h i2 D+ F4 v# k
else printf("%d不是素数",m);
; I: g, H, G6 n
}
' m4 K- D! Q ]( X; G1 b
作者:
081270053
时间:
2010-11-8 18:34
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:34
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:35
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:35
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:35
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:35
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:36
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:36
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:36
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 18:38
手机回复的，不是故意的，见谅
作者:
小草远在天涯
时间:
2010-11-8 18:47
回复
081270053
的帖子
5 T8 Q. i7 y; ^; o6 j8 M' L0 ?
; E0 G% Y$ X; R) {+ c
0 ?' B" S. ?. O, O& `
吓我一跳。没事，讲明原因，我不介意。是这样啊，那个程序我有点看不懂，而且又难背，所以自编一个来应付考试。
作者:
小草远在天涯
时间:
2010-11-8 18:51
回复
081270053
的帖子
: C& F& E$ R+ f
. X! B9 c* H! z' l4 \ \4 j" F( Z& N G
还要讲效率，对的，我忘了，没办法，书上的程序实在看不懂，不知道怎么判断的？劳烦你有空上网时回复我。我不急。谢谢。
% d- `, j: b2 j# }! P; a; R
作者:
weiyi0822
时间:
2010-11-8 20:53
..........................
作者:
岑亮
时间:
2010-11-8 21:35
m如果不是素数，总可以表示成两个整数的乘积m=s*t, s和t中总有一个<=m,所以<sqrt(m)的数中总有一个可以被m整除
作者:
安树庭
时间:
2010-11-8 21:44
循环到sqrt（m）就可以了，不需要到m
作者:
haobo
时间:
2010-11-8 22:11
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
$ A7 Y- p6 P* D, [* w
081270053 发表于 2010-11-8 18:36
8 w" O# [ n% q
同意
1 `# {) ~( q* a0 _! v
) i. G/ U8 w6 {/ d4 ` B3 y1 h
作者:
pengyumath
时间:
2010-11-8 22:54
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 23:42
这样：
9 H) b+ }3 d$ x5 v: ^! y2 i4 @+ ?
1、一个数对不是1或本身的任意一个数整除。你的程序利用x计算了它能整除的个数，然后判断；书上的程序是只要出现1个这样的约数，这个数就是合数就不用再判断了。用到了break节省运算次数。
) T' S, ]( p' M% h/ Y
2、范围上这个约数最大可能是sqrt（m）即这个数的平方根，所以没有可能是sqrt（m）到m之间的值，就不用运算这部分，又节省了效率。
作者:
小草远在天涯
时间:
2010-11-9 16:14
回复
岑亮
的帖子
, l* y. n9 \- _+ R" ^6 s! A: z
! ]9 u$ U+ s/ b: o6 {
. B; B* h+ {, P' Y
" 总可以表示成两个整数的乘积m=s*t, s和t中总有一个<=m,"这个让我更加懂了，谢谢。我总算搞懂了，要不然又要死记硬背了，我最讨厌这个了。太感谢了。
作者:
小草远在天涯
时间:
2010-11-9 16:18
回复
安树庭
的帖子
, G4 _; m; X+ N" B# n7 b
5 k! a, {# d. z2 A
# ?- W& G. X- [" n: p+ D2 O* h
我正纠结的是为什么是sqrt（m)，而不是m/2，或者m/4。。。。岑亮的回复让我彻底懂了该程序。这个程序我不知背了几回，过了几天又忘了，没有消化的知识不宜长期。
作者:
小草远在天涯
时间:
2010-11-9 16:19
回复
081270053
的帖子
( T1 X6 E& _+ Q. b
: x) W* k8 A3 \& w: J- |2 f; F
# x/ s6 d2 E* |) ?
小草已经知道了，岑亮的回复已经让我彻底懂了该程序。谢谢版主。
作者:
081270053
时间:
2010-11-9 22:18
回复
小草远在天涯
的帖子
+ r+ f( ?8 _4 u8 U1 ~
没事，呵呵。
. ~1 G( Y4 \: r" Q9 S
4 @+ R) N3 d( Z5 G" b
作者:
ksp
时间:
2010-11-10 19:19
其实仔细想想还可以优化一下， 偶数不可能是素数，所以偶数可以不算，这样计算量可以提高一半，i= 3， i<sqrt(m) +1; i+=2;不过得先判断一下 m == 2 ？ ，哈哈
作者:
小草远在天涯
时间:
2010-11-10 19:26
回复
ksp
的帖子
) t# x, p. s5 S
哇哦，不错啊。胜过教材呢！你检验过了吗？我先检验一下，我感觉挺好的。成功的话，再通知你，你可以去发邮件给出版社。
7 y$ J( e" _- O! E8 B
作者:
小草远在天涯
时间:
2010-11-10 20:40
本帖最后由 小草远在天涯 于 2010-11-10 21:57 编辑
- g; ]4 _! y1 A1 @7 C
G: p) h5 A$ X/ |3 b b" O {
回复
ksp
的帖子
7 G# {9 o$ }8 E: n
]) v" Z( I i+ l4 o
我在检验的过程中发现问题了，仔细想想，你这想法是不错，不过还是原题效率高。我把教材程序用流程图画出来，这样更清晰一点。你会领悟出来的，我不多说了。
9 w: T, C1 c. d+ N/ U! Y
作者:
小草远在天涯
时间:
2010-11-10 21:54
, X+ y, N$ F, H9 L0 L7 `
2010-11-10 21:52 上传
下载附件
(491.24 KB)
- R9 j' H3 w( R2 E6 L
作者:
ksp
时间:
2010-11-11 20:35
回复
小草远在天涯
的帖子
, D9 \+ ~$ V0 b h' h3 Y) Y
很对不起啊 ，我那个方法是生成素数的算法，我大意了。。囧了！
" ~5 @# X( ?) y- p
* }5 r9 M0 h9 T% V) X' }
作者:
小草远在天涯
时间:
2010-11-11 21:45
回复
ksp
的帖子
* c+ h d# Y' d$ K+ b+ r6 L, l
N# T8 _- y! Z' h. J
没关系。这根本没什么的。不要放在心上。敢说，不要怕错，没什么的。我一开始也不是一样的吗！
7 `6 M0 \% ^" e1 w" z' V+ [' @
作者:
ksp
时间:
2010-11-12 20:51
回复
小草远在天涯
的帖子
- n# U) D3 e t \$ p+ f
恩，向你学习！
% s6 m w2 c( z$ N# p
* E2 W7 e* y1 D1 o% m8 V
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
