数学建模社区-数学中国

标题: 判断一个数是否为素数（自编的） [打印本页]
作者: 小草远在天涯    时间: 2010-11-8 18:17
标题: 判断一个数是否为素数（自编的）
本帖最后由 小草远在天涯 于 2010-11-8 18:48 编辑
) N* r) o# b4 P6 E# H, W# t2 t
/ P1 @* ]" _5 a3 u! `#include "stdio.h"* o7 a2 s9 o3 Z- ~
main()
  F7 V# L6 m0 |  K; M7 }) ~1 L{
- G3 h3 a1 N& p1 ]4 fint m,i,x;
6 Z' L; W: o% }% p7 Ax=0;9 U, m) h2 d# s! ~/ G4 C
scanf("%d",&m);
/ I. U, n9 V) q3 U0 p; Y/ @for(i=1;i<=m;i++)
; K3 y& ~0 p% G" d9 f' v{
1 G7 b# M/ O8 D- x* \7 \6 q, D  if(m%i==0)
) D! w: t+ B' e1 v0 k& P4 K   x+=1;! ?7 A8 b4 R& j* t: S# B! B
}
4 w" e1 c9 X0 d. [0 tif(x>2). ?# o! V/ B" G0 z' x
  printf("该数不是素数！");: [& e& B6 c: R
else
2 D- o3 e5 Q& ^0 i  printf("该数是素数！");
: S# w- F' Y( t" o5 ~0 S}
7 E- m6 S. ~3 _, b1 w+ a思路：素数就是除了1和它本身之外不能被除的整数。也就是说素数只能被两个数相除，一个是1，另一个是它本身。那就简单了，只要判断是否有1和它本身之外的数，就行了。
) b7 f9 w. q9 p4 N9 d% A教材上在搞什么啊！我到现在还是不明白，真是看不懂！7 v+ |2 [. q% [, X& S2 R! `
我教材的程序是这样的。" C( _) b: m1 Y$ A8 D( V& x# ~
#include "stdio.h"
! F( {  ~6 }) b+ j, r. S#include "math.h"
/ Q, f7 c1 O3 R: D  Xmain(). d, G) K8 W& }& F/ ]. \: Q
{
! w9 e- y2 V+ A* S* \$ Nint m,i,x;
9 w8 l3 Z6 m  S7 }7 Z4 T: j4 T; C+ ~scanf("%d",&m);
$ V& U% W5 h6 d9 [$ L1 l* Y" Px=sqrt(m);5 F) r' X( N; d. j' o
for(i=2;i<=x;i++)8 W, V! O4 h4 Z% V) {/ z
  if(m%i==0)break;
. K7 @; X- s4 M8 R  if(i>x)printf("%d是素数",m);
; `5 o! p& Q2 I" A$ @  W+ k1 Y  else printf("%d不是素数",m);
' ?3 S$ o! @( {}
( r. d% e! E* v+ N2 b- v- I# u
作者: 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 的帖子2 Z* B  k% f  s. n$ |' ]! H0 ]
7 K' F8 f7 X$ |1 O7 L4 o
" w+ k5 d7 O' A' n$ o
吓我一跳。没事，讲明原因，我不介意。是这样啊，那个程序我有点看不懂，而且又难背，所以自编一个来应付考试。
作者: 小草远在天涯    时间: 2010-11-8 18:51
回复 081270053 的帖子- c3 s+ O6 g$ W( @3 e0 I
' F: `9 y" ]) F4 ]( n
还要讲效率，对的，我忘了，没办法，书上的程序实在看不懂，不知道怎么判断的？劳烦你有空上网时回复我。我不急。谢谢。8 }. U. N$ |* s6 Y. h
   
作者: 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全走一遍2 a: X- g& m/ }5 H' N
081270053 发表于 2010-11-8 18:36
/ B2 p# n( {5 w  N
同意
5 G* q+ D9 ^/ Q& g/ E  {' m% o6 r- W/ _+ G
作者: pengyumath    时间: 2010-11-8 22:54
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者: 081270053    时间: 2010-11-8 23:42
这样：- f& O4 @0 I+ L0 |) Z
1、一个数对不是1或本身的任意一个数整除。你的程序利用x计算了它能整除的个数，然后判断；书上的程序是只要出现1个这样的约数，这个数就是合数就不用再判断了。用到了break节省运算次数。
$ Q0 H7 ^7 E2 c* {+ i6 z2、范围上这个约数最大可能是sqrt（m）即这个数的平方根，所以没有可能是sqrt（m）到m之间的值，就不用运算这部分，又节省了效率。
作者: 小草远在天涯    时间: 2010-11-9 16:14
回复 岑亮 的帖子/ V: w; M6 T/ s% {3 c

$ `  m# j' ?4 s
3 O. n( [7 E7 T  X6 D/ h   " 总可以表示成两个整数的乘积m=s*t, s和t中总有一个<=m,"这个让我更加懂了，谢谢。我总算搞懂了，要不然又要死记硬背了，我最讨厌这个了。太感谢了。
作者: 小草远在天涯    时间: 2010-11-9 16:18
回复 安树庭 的帖子5 F6 `& v, [+ \) q

6 f6 I; H+ c- F. j: O7 S. f& ^
. d  T0 T& R& e. P5 F    我正纠结的是为什么是sqrt（m)，而不是m/2，或者m/4。。。。岑亮的回复让我彻底懂了该程序。这个程序我不知背了几回，过了几天又忘了，没有消化的知识不宜长期。
作者: 小草远在天涯    时间: 2010-11-9 16:19
回复 081270053 的帖子
. n' T2 \" i" B( ?- a5 ]2 |, d( O& K# g
  W! u! y& |1 L" {
    小草已经知道了，岑亮的回复已经让我彻底懂了该程序。谢谢版主。
作者: 081270053    时间: 2010-11-9 22:18
回复 小草远在天涯 的帖子
2 G7 e; X1 B% W+ Q没事，呵呵。# R7 O% @, u( Z. c
1 g7 X# [/ r" I7 e9 x
   
作者: ksp    时间: 2010-11-10 19:19
其实仔细想想还可以优化一下， 偶数不可能是素数，所以偶数可以不算，这样计算量可以提高一半，i= 3， i<sqrt(m) +1; i+=2;不过得先判断一下 m == 2 ？ ，哈哈
作者: 小草远在天涯    时间: 2010-11-10 19:26
回复 ksp 的帖子) S1 R9 W! n6 J2 @+ y' l, k
哇哦，不错啊。胜过教材呢！你检验过了吗？我先检验一下，我感觉挺好的。成功的话，再通知你，你可以去发邮件给出版社。
0 y& D' K' W/ ]; H2 D( C/ M9 R   
作者: 小草远在天涯    时间: 2010-11-10 20:40
本帖最后由 小草远在天涯 于 2010-11-10 21:57 编辑 / B6 j; q6 }7 u  U5 L  m

; a' y  B$ ?. l3 U  `5 B- ~# ?" Z/ X# |回复 ksp 的帖子
. z  R1 m# t* O6 ^! x* `" J! O& k! W1 }0 A
我在检验的过程中发现问题了，仔细想想，你这想法是不错，不过还是原题效率高。我把教材程序用流程图画出来，这样更清晰一点。你会领悟出来的，我不多说了。2 T. g0 Q- _% X4 C) G+ b6 u
   
作者: 小草远在天涯    时间: 2010-11-10 21:54
9 p  R( U# R9 I. r( A' _! [) R
未命名.bmp
, i/ |/ X" Y) _1 o* |% H
作者: ksp    时间: 2010-11-11 20:35
回复 小草远在天涯 的帖子
% i0 w' @& }, w* d1 {( e很对不起啊 ，我那个方法是生成素数的算法，我大意了。。囧了！" {- Q  a/ a% m5 m; R
7 x6 ^* U7 ]' k, _' o/ J5 q
   
作者: 小草远在天涯    时间: 2010-11-11 21:45
回复 ksp 的帖子
) ~  f$ f3 k- m/ Q4 K. E2 g$ p
6 N+ Z0 A2 z0 `. k$ e3 t: l  L没关系。这根本没什么的。不要放在心上。敢说，不要怕错，没什么的。我一开始也不是一样的吗！
1 `# _! G' V2 k; v   
作者: ksp    时间: 2010-11-12 20:51
回复 小草远在天涯 的帖子
( Y# A$ a/ J, t+ [4 V1 x# {" S恩，向你学习！9 d# y6 ]5 H' k# y7 M, X6 p
) d( L0 m% ]5 k: d
   



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5