数学建模社区-数学中国
标题:
判断一个数是否为素数（自编的）
[打印本页]
作者:
小草远在天涯
时间:
2010-11-8 18:17
标题:
判断一个数是否为素数（自编的）
本帖最后由 小草远在天涯 于 2010-11-8 18:48 编辑
) f4 `( j) z4 a6 z, ?; h2 i' h' x
! o) H F7 a, V# @: A$ F
#include "stdio.h"
2 P/ T4 |; c3 b
main()
0 E! |9 [3 o# D. e2 S' |9 Y
{
, n5 K, K/ k, @
int m,i,x;
! z5 h% ^2 E) o, N5 @( ^' M
x=0;
% C L8 U0 O2 R
scanf("%d",&m);
5 p6 G6 b/ ^: ]5 R2 G0 F
for(i=1;i<=m;i++)
/ a: U3 n- ~, u
{
' L) I: J* `( Y* [5 B
if(m%i==0)
& P9 l/ g# e" X( A
x+=1;
# L0 C' K H$ t# E' L( l Q
}
% V/ ~1 [! ?0 O' p
if(x>2)
. h- P9 T0 ~. G! l T' B6 u _' B- q
printf("该数不是素数！");
. g' G! J7 L3 B# r1 p, g7 v* `
else
( ?$ i2 |' c1 E
printf("该数是素数！");
e2 G; y& U7 Y# e9 D& s3 K& q
}
! r7 Y% |( H& v9 }* r0 x
思路：素数就是除了1和它本身之外不能被除的整数。也就是说素数只能被两个数相除，一个是1，另一个是它本身。那就简单了，只要判断是否有1和它本身之外的数，就行了。
! _% ~7 ~$ L- y9 E
教材上在搞什么啊！我到现在还是不明白，真是看不懂！
+ d6 X1 `& L9 F* e
我教材的程序是这样的。
* \) m9 {/ v8 A) J9 l- C
#include "stdio.h"
( y2 Z4 V. Z; I! ?" w
#include "math.h"
/ W- s4 G- \; ?6 ?
main()
" Y) Q: O; Z: u9 Y! T
{
" u7 v3 e% B5 |+ { J; X
int m,i,x;
. A% P, F0 Q& Z* R: V( {
scanf("%d",&m);
- f! q/ F/ O% K& ^/ ]& i4 B
x=sqrt(m);
, C9 M: o* r2 b; X+ A p/ }2 u
for(i=2;i<=x;i++)
( t$ A' [* a+ f
if(m%i==0)break;
) C# c! W, G! \ H1 c
if(i>x)printf("%d是素数",m);
1 \( j& e; R+ G- {# G0 G. c
else printf("%d不是素数",m);
4 e- M" `. l" P) c& J9 k, O9 `* m
}
0 g- h' \, \5 f4 X7 O* p
作者:
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
的帖子
1 n: d: H/ y( [) v% r* p
5 i+ [! F1 B9 C; m
0 F1 Q8 x ^" V I
吓我一跳。没事，讲明原因，我不介意。是这样啊，那个程序我有点看不懂，而且又难背，所以自编一个来应付考试。
作者:
小草远在天涯
时间:
2010-11-8 18:51
回复
081270053
的帖子
_0 M; o4 @* @
# Y. A: H7 g x
还要讲效率，对的，我忘了，没办法，书上的程序实在看不懂，不知道怎么判断的？劳烦你有空上网时回复我。我不急。谢谢。
* q8 e& h. Q. I6 z: R; b
作者:
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全走一遍
; k. b: \+ A* ?" N9 B
081270053 发表于 2010-11-8 18:36
2 O/ X) F7 y# E. f& B
同意
5 \, f( {( i/ u7 Q! I
i0 K V5 p. e: a* h
作者:
pengyumath
时间:
2010-11-8 22:54
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者:
081270053
时间:
2010-11-8 23:42
这样：
$ Q$ H, p2 M: P$ c6 m* g
1、一个数对不是1或本身的任意一个数整除。你的程序利用x计算了它能整除的个数，然后判断；书上的程序是只要出现1个这样的约数，这个数就是合数就不用再判断了。用到了break节省运算次数。
/ [- t0 l; f4 d+ D9 K0 w
2、范围上这个约数最大可能是sqrt（m）即这个数的平方根，所以没有可能是sqrt（m）到m之间的值，就不用运算这部分，又节省了效率。
作者:
小草远在天涯
时间:
2010-11-9 16:14
回复
岑亮
的帖子
5 P, I& `. f3 y8 {3 c. k' B" f
( g# Q: m/ k8 m, F4 N) \4 N
4 E. B. D' G( [# m1 {4 D
" 总可以表示成两个整数的乘积m=s*t, s和t中总有一个<=m,"这个让我更加懂了，谢谢。我总算搞懂了，要不然又要死记硬背了，我最讨厌这个了。太感谢了。
作者:
小草远在天涯
时间:
2010-11-9 16:18
回复
安树庭
的帖子
3 H" `3 B; d$ v( L0 {2 e
+ H: ^1 B7 T- W9 c7 ^+ a5 @
3 K# @/ G2 ?. |( ~9 f& c
我正纠结的是为什么是sqrt（m)，而不是m/2，或者m/4。。。。岑亮的回复让我彻底懂了该程序。这个程序我不知背了几回，过了几天又忘了，没有消化的知识不宜长期。
作者:
小草远在天涯
时间:
2010-11-9 16:19
回复
081270053
的帖子
# d" f6 z3 ^8 c7 U# @
+ [2 q7 l) I9 Z# W0 U
0 v _1 M& a' ^: B
小草已经知道了，岑亮的回复已经让我彻底懂了该程序。谢谢版主。
作者:
081270053
时间:
2010-11-9 22:18
回复
小草远在天涯
的帖子
3 x" i5 j5 d. n# a% D5 [
没事，呵呵。
1 _- Q& z: Q. x& D# M+ Z5 N
% \! K! l6 M- k( X- W0 Q
作者:
ksp
时间:
2010-11-10 19:19
其实仔细想想还可以优化一下， 偶数不可能是素数，所以偶数可以不算，这样计算量可以提高一半，i= 3， i<sqrt(m) +1; i+=2;不过得先判断一下 m == 2 ？ ，哈哈
作者:
小草远在天涯
时间:
2010-11-10 19:26
回复
ksp
的帖子
1 N- o0 b( T9 r+ ?
哇哦，不错啊。胜过教材呢！你检验过了吗？我先检验一下，我感觉挺好的。成功的话，再通知你，你可以去发邮件给出版社。
]2 V% |/ J; J" k1 ~
作者:
小草远在天涯
时间:
2010-11-10 20:40
本帖最后由 小草远在天涯 于 2010-11-10 21:57 编辑
* x/ |- Q/ X* j% Z' _5 ?9 {4 P: K; W- Q
+ a7 S U; M8 O* I
回复
ksp
的帖子
7 B; U7 ~3 j2 T+ R6 l, y3 ?5 M
% f1 |3 e# q9 [3 v+ J
我在检验的过程中发现问题了，仔细想想，你这想法是不错，不过还是原题效率高。我把教材程序用流程图画出来，这样更清晰一点。你会领悟出来的，我不多说了。
; ]4 Z" G4 u: D3 ^9 r
作者:
小草远在天涯
时间:
2010-11-10 21:54
p+ |/ ?1 U0 S) f- M7 B, I8 E3 X" F
2010-11-10 21:52 上传
下载附件
(491.24 KB)
) C6 Z# b* B @- u. K
作者:
ksp
时间:
2010-11-11 20:35
回复
小草远在天涯
的帖子
$ J- S6 R" a; M1 v
很对不起啊 ，我那个方法是生成素数的算法，我大意了。。囧了！
# D& B- J4 u7 n+ |
2 S2 v* j' a: A5 P- j# s j/ @
作者:
小草远在天涯
时间:
2010-11-11 21:45
回复
ksp
的帖子
# j3 S L. M5 B+ t; b# d
! _* |6 _& a& R! y! J/ q q, g
没关系。这根本没什么的。不要放在心上。敢说，不要怕错，没什么的。我一开始也不是一样的吗！
1 ]0 n+ f' M; r1 j
作者:
ksp
时间:
2010-11-12 20:51
回复
小草远在天涯
的帖子
5 X& p x) y7 l& ~( f
恩，向你学习！
7 [1 C/ s$ B! u: M, F$ h
5 E; H2 W6 R6 q |2 l8 G
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
