数学建模社区-数学中国

标题: 判断一个数是否为素数(自编的) [打印本页]

作者: 小草远在天涯    时间: 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' pif(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; Xint m,i,x;
. A% P, F0 Q& Z* R: V( {scanf("%d",&m);
- f! q/ F/ O% K& ^/ ]& i4 Bx=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* p5 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 B081270053 发表于 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 未命名.bmp ) 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