数学建模社区-数学中国
标题:
判断一个数是否为素数（自编的）
[打印本页]
作者:
小草远在天涯
时间:
2010-11-8 18:17
标题:
判断一个数是否为素数（自编的）
本帖最后由 小草远在天涯 于 2010-11-8 18:48 编辑
& I! h, W$ J- ]7 ~1 g& Q3 J& j; ^
8 z V# J6 L/ M7 u6 g, P
#include "stdio.h"
' }- M8 v8 D, Q0 e
main()
) i) a. O+ t8 O- a2 t. |
{
- g5 W1 b+ z# d5 |. X5 d U
int m,i,x;
( H1 I) K, ?+ I
x=0;
+ [: D- H4 `2 m1 T# |
scanf("%d",&m);
# F/ V* G' ~( {; o
for(i=1;i<=m;i++)
. n3 t9 p! I1 I, r) A( [" k8 f
{
- a" s! H/ A4 U6 M. u
if(m%i==0)
& K, s M% C* S* i" k9 S1 q
x+=1;
& ^6 E {) z- v p: Y8 G$ ^
}
7 W1 m: c0 y& l b" h1 ] P
if(x>2)
5 E! M' p4 G) M6 `! w) ?$ k' a
printf("该数不是素数！");
# E: }+ P, _8 U& P
else
]& t1 w4 [/ d# L( ]) B" I
printf("该数是素数！");
+ y9 I, @3 `$ J
}
+ {1 M2 Q/ m3 H% B4 x4 \+ w
思路：素数就是除了1和它本身之外不能被除的整数。也就是说素数只能被两个数相除，一个是1，另一个是它本身。那就简单了，只要判断是否有1和它本身之外的数，就行了。
/ l8 `2 q1 {1 x- W) Z5 x( L' ]1 K
教材上在搞什么啊！我到现在还是不明白，真是看不懂！
; O% u' J4 S: z' n5 h
我教材的程序是这样的。
: R. F) [( D& X# t7 g' i
#include "stdio.h"
; M$ R2 M+ @: f# W3 p+ i
#include "math.h"
. ^1 d w9 S2 [6 f* Y- y
main()
7 [6 ~: L9 p. Z `
{
2 l# h, Q8 A) m
int m,i,x;
1 [4 p, r. x2 H7 e
scanf("%d",&m);
7 |, c2 C% R4 p: U) b6 j6 e
x=sqrt(m);
' I2 H5 V( R, X" _( ^0 O* ~
for(i=2;i<=x;i++)
0 x1 n4 [7 o- l. L
if(m%i==0)break;
+ o% N* n- q) y* f+ a" M
if(i>x)printf("%d是素数",m);
/ ?+ T7 `& ~- R# x0 v0 R7 r" \/ |
else printf("%d不是素数",m);
2 q* i9 ~1 ^; Y: m0 l c
}
' R2 X% @5 s0 m
作者:
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
的帖子
& C" ^* _* D$ x! Z: C) K' ^ K$ D" C
5 ]1 R% v5 j" [) F2 f/ z n
' v; K' H7 W. c8 a4 G7 f
吓我一跳。没事，讲明原因，我不介意。是这样啊，那个程序我有点看不懂，而且又难背，所以自编一个来应付考试。
作者:
小草远在天涯
时间:
2010-11-8 18:51
回复
081270053
的帖子
1 K6 {* W4 Z0 G5 w& u
3 ?6 S' }+ L. O/ j% M2 K" ]
还要讲效率，对的，我忘了，没办法，书上的程序实在看不懂，不知道怎么判断的？劳烦你有空上网时回复我。我不急。谢谢。
/ T( B0 _$ B% i! `% a; W X
作者:
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全走一遍
' m I8 w; B) {: ] D
081270053 发表于 2010-11-8 18:36
. t4 F% C- b0 d# ?& `
同意
( A/ z. H$ O% \! D! ^
; K- e, I% e( y$ g
作者:
pengyumath
时间:
2010-11-8 22:54
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 23:42
这样：
( S/ L: l e7 N9 z8 [* U
1、一个数对不是1或本身的任意一个数整除。你的程序利用x计算了它能整除的个数，然后判断；书上的程序是只要出现1个这样的约数，这个数就是合数就不用再判断了。用到了break节省运算次数。
8 H2 j/ g! t* G$ D( g+ X8 s
2、范围上这个约数最大可能是sqrt（m）即这个数的平方根，所以没有可能是sqrt（m）到m之间的值，就不用运算这部分，又节省了效率。
作者:
小草远在天涯
时间:
2010-11-9 16:14
回复
岑亮
的帖子
! Y& _* d, D4 y. u/ f: S
9 z5 b8 V/ {7 p! W
% |( U( n, N7 N+ Z; G5 r
" 总可以表示成两个整数的乘积m=s*t, s和t中总有一个<=m,"这个让我更加懂了，谢谢。我总算搞懂了，要不然又要死记硬背了，我最讨厌这个了。太感谢了。
作者:
小草远在天涯
时间:
2010-11-9 16:18
回复
安树庭
的帖子
' J, f7 r5 C) D: V( Z2 Y+ F, p: @9 ?
* V. X' k3 k2 q$ w, d* q
1 @6 P @* _+ |* p& e$ N- d
我正纠结的是为什么是sqrt（m)，而不是m/2，或者m/4。。。。岑亮的回复让我彻底懂了该程序。这个程序我不知背了几回，过了几天又忘了，没有消化的知识不宜长期。
作者:
小草远在天涯
时间:
2010-11-9 16:19
回复
081270053
的帖子
3 B6 X5 m0 @0 h' |2 x6 H
- E+ H% E, G# z. \& u, v% k. ?, o
: f7 Z0 Y5 J2 ^$ J0 o
小草已经知道了，岑亮的回复已经让我彻底懂了该程序。谢谢版主。
作者:
081270053
时间:
2010-11-9 22:18
回复
小草远在天涯
的帖子
, c4 L0 a6 B7 K3 A! g
没事，呵呵。
8 V4 u& {( k7 u
6 b( r+ P% U1 m* F( ^( B0 P
作者:
ksp
时间:
2010-11-10 19:19
其实仔细想想还可以优化一下， 偶数不可能是素数，所以偶数可以不算，这样计算量可以提高一半，i= 3， i<sqrt(m) +1; i+=2;不过得先判断一下 m == 2 ？ ，哈哈
作者:
小草远在天涯
时间:
2010-11-10 19:26
回复
ksp
的帖子
# P4 U6 v. q$ u" V; ^- r
哇哦，不错啊。胜过教材呢！你检验过了吗？我先检验一下，我感觉挺好的。成功的话，再通知你，你可以去发邮件给出版社。
7 l. y d {, i5 {1 r0 u+ d2 @3 ~+ W! e
作者:
小草远在天涯
时间:
2010-11-10 20:40
本帖最后由 小草远在天涯 于 2010-11-10 21:57 编辑
6 n: l3 V7 @3 w: |! h; I
: }$ W2 c! V! _) z: ^
回复
ksp
的帖子
$ C9 N, n/ X2 Q; g8 ^
, @/ ~& f, U* k: n% A0 J
我在检验的过程中发现问题了，仔细想想，你这想法是不错，不过还是原题效率高。我把教材程序用流程图画出来，这样更清晰一点。你会领悟出来的，我不多说了。
3 H3 l& f: O, ?: N+ P
作者:
小草远在天涯
时间:
2010-11-10 21:54
2 l: o& z: s, x1 R) Z
2010-11-10 21:52 上传
下载附件
(491.24 KB)
& f0 ~. z3 D" Z
作者:
ksp
时间:
2010-11-11 20:35
回复
小草远在天涯
的帖子
, z2 c- P d* Z7 z; U3 u: w# h2 q
很对不起啊 ，我那个方法是生成素数的算法，我大意了。。囧了！
5 T5 r2 X3 U* y3 @/ {0 M- v" F
4 \" a( V n; D1 I# t$ @
作者:
小草远在天涯
时间:
2010-11-11 21:45
回复
ksp
的帖子
+ Q" g# y8 N- W! ?* o
8 f1 F1 s3 d8 A- {3 z3 U. c% X
没关系。这根本没什么的。不要放在心上。敢说，不要怕错，没什么的。我一开始也不是一样的吗！
( K9 o9 p9 Y4 X2 R" E5 _$ \1 B
作者:
ksp
时间:
2010-11-12 20:51
回复
小草远在天涯
的帖子
& r/ e8 |5 ^; v
恩，向你学习！
5 q5 k: S+ M4 U# P) |! Q
! T& ?( v, ?5 Z5 E k
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
