烦恼~怎么判断1个正整数是不是素数的问题?
问题描述:
烦恼~怎么判断1个正整数是不是素数的问题?
1个正整数n,只须被2到n/2之间的整数除,如都除不尽,n必为素数.
这是为什么?为什么只须被2到n/2之间的数除,除不尽就能断定n是素数,而不需要检验n/2到n之间的整数.
为什么2到n/2之间除不尽,n/2到n之间肯定也除不尽,就这点弄不明白.不太理解啊.
那怎么能证明呢?
答
n除以n/2至n之间的任意一个数的结果肯定是一个在1和2之间的小数,不符合2到n/2之间的要求(结果和除数互为因数),再一个不符合除尽的要求,所以不用除了,直接排除.