数学建模社区-数学中国

标题: 判断一个数是否为素数（自编的） [打印本页]
作者: 小草远在天涯    时间: 2010-11-8 18:17
标题: 判断一个数是否为素数（自编的）
本帖最后由 小草远在天涯 于 2010-11-8 18:48 编辑
4 p4 z. h/ R, Q. S
: N  X$ T' j/ A% q& g# s1 g9 D#include "stdio.h"2 c2 G4 U$ H9 s; t
main()% O4 L9 t) ~( \$ Q( G
{
, t6 s$ Q3 @4 ]' p: n( o4 [int m,i,x;
" E$ }% Z4 \  g" Zx=0;
& I* ^/ o/ i# G9 d5 W( p9 jscanf("%d",&m);
# W/ P1 E  Y0 Ufor(i=1;i<=m;i++)& ?: G9 L. S6 v2 D
{
5 S/ q' k' y( u  if(m%i==0)
" X4 F$ f8 r- a/ c- t) w) Q( x   x+=1;
: i$ q" x5 n8 u+ S- f}6 ^' C) H( o: b+ A% g! j  b3 K
if(x>2)" u/ x7 i" e3 v: f
  printf("该数不是素数！");) x) A* k1 g$ A; ~7 Q
else
* K1 i  }/ }8 x7 j4 d  printf("该数是素数！");$ p7 A0 G! z3 w- D+ N5 l
}
0 s$ D. d) b3 U; V+ C5 C" E  K思路：素数就是除了1和它本身之外不能被除的整数。也就是说素数只能被两个数相除，一个是1，另一个是它本身。那就简单了，只要判断是否有1和它本身之外的数，就行了。9 J) n; T& k# D+ [3 j
教材上在搞什么啊！我到现在还是不明白，真是看不懂！4 R" _/ P# H. _1 ?; |# Q
我教材的程序是这样的。
! u5 \9 c- M: U! t2 U3 L2 W6 K% ]" W#include "stdio.h"( ^5 }( j; L9 g% T& Y; S  p
#include "math.h"* ]$ Z$ |/ n$ v$ \
main()& F  o4 r: c6 j2 \( F
{
. S7 {8 q+ v) G! S$ l1 f6 fint m,i,x;
7 R: K4 n7 @2 D8 d; `( s& u5 |' }scanf("%d",&m);  c; u& x0 h$ t1 p, I: Z+ H
x=sqrt(m);" W. V' e; }4 ?
for(i=2;i<=x;i++)
: G# Q, h& t) d! S8 M/ `& e8 o& o  if(m%i==0)break;
- F! |$ z1 P( u7 u# P, k1 [  if(i>x)printf("%d是素数",m);2 I* f; g/ ?1 {; Z- y0 j
  else printf("%d不是素数",m);
7 q* c0 [+ I7 g' L}
. S$ w/ @  G* N& k$ N% N' ^% L+ X, r" C
作者: 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 的帖子  s% B% P# R* G$ K
4 c0 ]6 v+ n" a( I

2 u. g6 b' s0 N7 ]& z# v1 {$ U5 ? 吓我一跳。没事，讲明原因，我不介意。是这样啊，那个程序我有点看不懂，而且又难背，所以自编一个来应付考试。
作者: 小草远在天涯    时间: 2010-11-8 18:51
回复 081270053 的帖子
$ k$ b5 J1 x. j" b  s9 D4 C
# K1 ~% Y& W' a8 E. k) J还要讲效率，对的，我忘了，没办法，书上的程序实在看不懂，不知道怎么判断的？劳烦你有空上网时回复我。我不急。谢谢。
: d! K+ q# [- W. @) {' j   
作者: 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全走一遍5 b% O/ l, k1 ?6 p/ Y' X. }9 M) {$ y! x
081270053 发表于 2010-11-8 18:36
. w4 z  K8 ~# x  U0 W
同意; E! J- ~# r- D; c( P- i& ~! X

: ^- ^" i, E- v) P
作者: pengyumath    时间: 2010-11-8 22:54
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者: 081270053    时间: 2010-11-8 23:42
这样：5 |- Z' _: V/ b) m
1、一个数对不是1或本身的任意一个数整除。你的程序利用x计算了它能整除的个数，然后判断；书上的程序是只要出现1个这样的约数，这个数就是合数就不用再判断了。用到了break节省运算次数。
0 Z  J7 T4 N* Q2 O' C2、范围上这个约数最大可能是sqrt（m）即这个数的平方根，所以没有可能是sqrt（m）到m之间的值，就不用运算这部分，又节省了效率。
作者: 小草远在天涯    时间: 2010-11-9 16:14
回复 岑亮 的帖子7 m' w2 r7 a/ N* ~' [4 _
7 y6 l! U' n" o0 U; V' N
+ A, N  N, n! R( [
   " 总可以表示成两个整数的乘积m=s*t, s和t中总有一个<=m,"这个让我更加懂了，谢谢。我总算搞懂了，要不然又要死记硬背了，我最讨厌这个了。太感谢了。
作者: 小草远在天涯    时间: 2010-11-9 16:18
回复 安树庭 的帖子
* o; \( d1 T+ P0 ~
% e% q" T* i7 p8 D' Z
7 G+ I+ Y- b4 P" `$ t    我正纠结的是为什么是sqrt（m)，而不是m/2，或者m/4。。。。岑亮的回复让我彻底懂了该程序。这个程序我不知背了几回，过了几天又忘了，没有消化的知识不宜长期。
作者: 小草远在天涯    时间: 2010-11-9 16:19
回复 081270053 的帖子; T& D" Q0 j% P. u3 \; P( T
+ b# j) r: ^  r# o' S  b' s; d
, e  s3 R) J! z+ x% E7 t
    小草已经知道了，岑亮的回复已经让我彻底懂了该程序。谢谢版主。
作者: 081270053    时间: 2010-11-9 22:18
回复 小草远在天涯 的帖子; }) p' S8 o5 O9 |
没事，呵呵。
. r* W' x  H. ]* T( Q  D# w7 e, J* {  U% r: Y) x: J- J' S6 M
   
作者: ksp    时间: 2010-11-10 19:19
其实仔细想想还可以优化一下， 偶数不可能是素数，所以偶数可以不算，这样计算量可以提高一半，i= 3， i<sqrt(m) +1; i+=2;不过得先判断一下 m == 2 ？ ，哈哈
作者: 小草远在天涯    时间: 2010-11-10 19:26
回复 ksp 的帖子0 m( K+ V; h6 [: `3 v8 C: G" b) D$ a
哇哦，不错啊。胜过教材呢！你检验过了吗？我先检验一下，我感觉挺好的。成功的话，再通知你，你可以去发邮件给出版社。
/ H" Y, _; T$ H' b# j: k' V4 d   
作者: 小草远在天涯    时间: 2010-11-10 20:40
本帖最后由 小草远在天涯 于 2010-11-10 21:57 编辑 " I$ V  o/ h. ?0 Q

% q" \2 ~! g" i' m& f回复 ksp 的帖子
8 P0 G- S6 K& W( m" `+ m0 Y3 R, I  p8 s$ A8 _
我在检验的过程中发现问题了，仔细想想，你这想法是不错，不过还是原题效率高。我把教材程序用流程图画出来，这样更清晰一点。你会领悟出来的，我不多说了。
0 @, H# [- T! h# ~6 e% x1 F. A   
作者: 小草远在天涯    时间: 2010-11-10 21:54

- a7 d& ?7 b" y6 m# s7 r: O$ | 未命名.bmp ! b1 S: r! r( i% q
作者: ksp    时间: 2010-11-11 20:35
回复 小草远在天涯 的帖子
- f; V* [  d1 @& T/ c7 N2 M2 ]很对不起啊 ，我那个方法是生成素数的算法，我大意了。。囧了！
! e. C( u( I/ {" ]! b- p7 ]% W$ M- s7 I1 E& h4 c" u8 r4 |" M
   
作者: 小草远在天涯    时间: 2010-11-11 21:45
回复 ksp 的帖子7 v  \% i' o. D1 q5 m

0 j8 M$ G3 i. p  ^没关系。这根本没什么的。不要放在心上。敢说，不要怕错，没什么的。我一开始也不是一样的吗！" P% i' M2 ?+ o" a& K
   
作者: ksp    时间: 2010-11-12 20:51
回复 小草远在天涯 的帖子' t4 T* `6 x9 S" Z% r# n
恩，向你学习！
  ]! r+ ]: |: L+ p: T: m/ y! ^2 o( X% p* H) f
   



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