怎样判断一个数是不是质数?
正确而迅速地判断一个自然数是不是质数,在数的整除性这部分知识中,是一项重要的基本技能.
由于大于2的质数一定是奇数(奇数又不一定都是质数),所以,在判断一个自然数是不是质数时,首先要看它是奇数还是偶数.如果是大于2的偶数,这个数肯定不是质数,而是合数;如果是奇数,那就有可能是质数.在这种情况下,一般使用以下两种方法:
1、查
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
法:
主要是指查“质数表”.编制质数表的过程是:按照自然数列,第一个数1不是质数,因此要除外,然后按顺序写出2至500的所有自然数,这些数中2是质数,把它留下,把2后面所有2的倍数划去,2后面的3是质数,接着再把3后面所有3的倍数划去,如此继续下去,剩下的便是500以内的全部质数.
最早使用上述方法来寻求质数的人,是古代希腊数学家埃拉托斯特尼,由于他在开始时,先把自然数写在一块蜡板上,把不是质数的数(合数)分别刺上一个孔,这样,在蜡板上就被刺上了许多象筛子一样的孔,后来,大家就把这种寻求质数的方法叫做“筛法”.
?/P>
这类的质数表还可以编制成数字范围更大一些的,如1000以内质数表等.判断一个自然数是不是质数,如在表所规定的数字范围内,即可用查表的方法进行判断.
2、试除法:
在手头上没有质数表的情况下,可以用试除法来判断一个自然数是不是质数.例如判断143、179是不是质数,就可以按从小到大的顺序用2、3、5、7、11……等质数去试除.一般情况下用20以内的2、3、5、7、11、13、17、19这8个质数去除就可以了.如143,这个数的个位是3,排除了被2、5整除的可能性,它各位数字的和是1+4+3=8,也不可能被3整除,通过口算也证明不能被7整除,当试除到11时,商正好是13,到此就可以断定143不是质数.
对179试除过程如下:
179÷2=59……2
179÷3=66……1
179÷5=35……4
179÷7=25……4
179÷11=16……3
179÷13=13……10
179÷17=10……9
当179÷17所得到的不完全商10比除数17小时,就不需要继续再试除,而断定179是质数.这是因为2、3、5、7、11、13、17都不是179的质因数,因此,179不会再有比17大的质因数,或者说179不可能被小于10的数整除,所以,179必是质数无疑.
综上所述,用试除法判断一个自然数a是不是质数时,只要用各个质数从小到大依次去除a,如果到某一个质数正好整除,这个a就可以断定不是质数;如果不能整除,当不完全商又小于这个质数时,就不必再继续试除,可以断定a必然是质数.
1000以内质数表(168个):
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997