数学建模社区-数学中国

标题: 判断一个数是否为素数（自编的） [打印本页]
作者: 小草远在天涯    时间: 2010-11-8 18:17
标题: 判断一个数是否为素数（自编的）
本帖最后由 小草远在天涯 于 2010-11-8 18:48 编辑 3 x/ w0 x  I2 |; j' U6 g% k0 z
4 e) z7 R1 x& K) t3 i
#include "stdio.h"
9 E5 F0 K" q5 j2 _4 F9 v9 gmain()
" ]1 R( E* S' N6 O, x) d{/ J8 P2 d4 I! g4 w3 g  W; S
int m,i,x;
, \% D0 N& @' a: B0 `' {x=0;
7 O" S8 C( Y' e. R! s# O) G" Kscanf("%d",&m);
0 _8 @7 h' s( a) ufor(i=1;i<=m;i++)" s7 |' d& i3 }- f: s  P& h
{& u. V) k. M9 G) e) H
  if(m%i==0)9 u# Y& @' q* F9 g, a
   x+=1;
& [9 N& e; d; a* j. _9 u; z/ i}5 [9 C( t$ ?. O5 q6 [
if(x>2)8 u) Y' r) v5 r
  printf("该数不是素数！");
5 T, B) Y+ s7 a9 V4 n. _* |& qelse
1 G6 [5 M. ^, W  printf("该数是素数！");
: h0 \. Z+ U: c$ }}; T/ \2 L( x6 X: v6 x
思路：素数就是除了1和它本身之外不能被除的整数。也就是说素数只能被两个数相除，一个是1，另一个是它本身。那就简单了，只要判断是否有1和它本身之外的数，就行了。
% m2 v# r* Q* s6 M教材上在搞什么啊！我到现在还是不明白，真是看不懂！! d5 c8 b2 r6 O/ L: h: N6 ]3 k
我教材的程序是这样的。
1 l/ p6 l' U, }( O) r4 \  ?$ W! D2 B#include "stdio.h"7 z# y( D3 q$ c+ r
#include "math.h"
8 t4 j) B# U6 _. z! L! bmain()8 h7 ~/ @4 {: w; i1 J) A
{& M6 v3 b9 \  x( V, A2 g/ k
int m,i,x;
* A% e5 _: p1 wscanf("%d",&m);
2 G- T" L$ t" z0 }$ p# Q) dx=sqrt(m);& ?) }6 Y+ j) U7 e0 F6 W- e
for(i=2;i<=x;i++)* ?9 Q9 B7 u* X8 V' C
  if(m%i==0)break;
" E& T/ J; v0 u0 y' ~, t/ Y* X  if(i>x)printf("%d是素数",m);$ s! }) U* [9 n; ]6 f5 F% E
  else printf("%d不是素数",m);
) e- Q. n# }# j; x' x}! P; G! ?. ]! O; _. f% ?2 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 的帖子, w1 `# {& ?! W( i

& p3 y7 I% B0 p- D5 U3 i: X& R' k9 H( N- u# ?, v
吓我一跳。没事，讲明原因，我不介意。是这样啊，那个程序我有点看不懂，而且又难背，所以自编一个来应付考试。
作者: 小草远在天涯    时间: 2010-11-8 18:51
回复 081270053 的帖子
" M- C, B' @! X* z9 d9 ~! s  ~% u8 I/ x% U
还要讲效率，对的，我忘了，没办法，书上的程序实在看不懂，不知道怎么判断的？劳烦你有空上网时回复我。我不急。谢谢。
& o6 m; b6 U. y2 ]- ]   
作者: 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 V5 Q7 {+ f; ]6 p8 S" v1 k( p0 P081270053 发表于 2010-11-8 18:36
, e$ [7 u* J6 M- S8 Y: \: T
同意
3 u  D# L; ]+ y5 y5 E/ U/ K" n5 D1 C2 D) C( d( b
作者: pengyumath    时间: 2010-11-8 22:54
后面的程序效率高，一个数最大的可能约数不会超过Sqrt(m),没有必要2--m-1全走一遍
作者: 081270053    时间: 2010-11-8 23:42
这样：, h7 U0 o/ v4 P3 [  e$ q
1、一个数对不是1或本身的任意一个数整除。你的程序利用x计算了它能整除的个数，然后判断；书上的程序是只要出现1个这样的约数，这个数就是合数就不用再判断了。用到了break节省运算次数。
5 s. z6 G- T" C$ D* k* T) T2 S# Y, ?2、范围上这个约数最大可能是sqrt（m）即这个数的平方根，所以没有可能是sqrt（m）到m之间的值，就不用运算这部分，又节省了效率。
作者: 小草远在天涯    时间: 2010-11-9 16:14
回复 岑亮 的帖子
8 q% m; c" f0 Y# L5 D2 w3 e
" f  [$ |* _% I# t4 x( s( `, o, m. R- @' {8 G$ _' D, _5 Z3 d+ O
   " 总可以表示成两个整数的乘积m=s*t, s和t中总有一个<=m,"这个让我更加懂了，谢谢。我总算搞懂了，要不然又要死记硬背了，我最讨厌这个了。太感谢了。
作者: 小草远在天涯    时间: 2010-11-9 16:18
回复 安树庭 的帖子
5 ^3 C$ R* j' w4 |5 O
1 c/ R5 X; `, ]6 Z; {: T& G5 ], e8 a0 U9 t& [
    我正纠结的是为什么是sqrt（m)，而不是m/2，或者m/4。。。。岑亮的回复让我彻底懂了该程序。这个程序我不知背了几回，过了几天又忘了，没有消化的知识不宜长期。
作者: 小草远在天涯    时间: 2010-11-9 16:19
回复 081270053 的帖子
( _. r6 n0 N7 Z2 V0 K8 j4 }2 V$ m# ], r
4 k5 ]; ?$ h. V* r& u# Z
    小草已经知道了，岑亮的回复已经让我彻底懂了该程序。谢谢版主。
作者: 081270053    时间: 2010-11-9 22:18
回复 小草远在天涯 的帖子* s9 C1 L5 {( r9 d
没事，呵呵。2 x* G1 P2 Q% M+ F/ ^; q

% l$ V" }" Y  o+ D   
作者: ksp    时间: 2010-11-10 19:19
其实仔细想想还可以优化一下， 偶数不可能是素数，所以偶数可以不算，这样计算量可以提高一半，i= 3， i<sqrt(m) +1; i+=2;不过得先判断一下 m == 2 ？ ，哈哈
作者: 小草远在天涯    时间: 2010-11-10 19:26
回复 ksp 的帖子$ R0 D7 g1 n! E2 @2 G( m% i8 b
哇哦，不错啊。胜过教材呢！你检验过了吗？我先检验一下，我感觉挺好的。成功的话，再通知你，你可以去发邮件给出版社。& A( v. [' c+ i+ k* S
   
作者: 小草远在天涯    时间: 2010-11-10 20:40
本帖最后由 小草远在天涯 于 2010-11-10 21:57 编辑 - I% E8 y$ I. o1 z1 r
! a$ w) j0 [  }! o! |$ A, l
回复 ksp 的帖子
" E9 q$ q5 y* _! s- o
3 @+ f& A: a  i" I6 {我在检验的过程中发现问题了，仔细想想，你这想法是不错，不过还是原题效率高。我把教材程序用流程图画出来，这样更清晰一点。你会领悟出来的，我不多说了。3 f6 ~1 a. A* O7 l" }4 ]
   
作者: 小草远在天涯    时间: 2010-11-10 21:54

& O% H4 z; S+ O 未命名.bmp
0 |1 N; p! P7 i& d
作者: ksp    时间: 2010-11-11 20:35
回复 小草远在天涯 的帖子
* Q) d/ e& @7 ]很对不起啊 ，我那个方法是生成素数的算法，我大意了。。囧了！
' e  W; N7 _- k) ]" Q/ {) m# E  R
8 }/ m0 }  _: E9 e% M4 T8 F   
作者: 小草远在天涯    时间: 2010-11-11 21:45
回复 ksp 的帖子
; T3 L9 x$ F5 w# c& t7 k# r6 T
& T+ h) B' L7 {7 n7 B8 X没关系。这根本没什么的。不要放在心上。敢说，不要怕错，没什么的。我一开始也不是一样的吗！$ |2 b& r' N3 y  m
   
作者: ksp    时间: 2010-11-12 20:51
回复 小草远在天涯 的帖子9 S1 s/ S5 k8 ~2 H$ R; v, j
恩，向你学习！
! _% \" Z/ y+ @% Y4 _# _* e& u8 D. m: Z( ]( X- p
   



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