素数判断?这不是小学学的吗?
您先别着急,不管您是小学,初中还是高中,从事什么职业,我相信,坚持看完你一定有收获!
对你有帮助别忘了给我点个赞哦~
我们要判断素数,首先要知道素数的定义。
素数:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。
知道了素数的定义,那么我们应该想一下,如何去判断一个数是否为素数?
一种思路是,我们在每次得到一个数后,都去计算,去尝试因式分解它,看它除了1和自身之外还有没有其他因子另一种是,我们去查阅素数表,看这个数在不在素数表上。那我们就要先得到素数表。
以下除了第一种方法,第2~4种方法都是用第二种思路做的当要判断的目标数很少时,第一种高效。但是当给定的目标数组很多,数也很大时。后面的思路配上高效的查找算法,显然更高效
方法1:暴力求解
1-1:稍微动动脑
思想:根据素数的定义思考。素数是大于1的自然数,除了1和自身外,其他数都不是它的因子。 那我们就可以用一个循环,从2开始遍历到这个数减去1,如果这个数都不能被整除,那么这个数就是素数。 也就是说: 给定一个数 n , i 从 2 开始取值,直到 n – 1(取整数),如果 n % i != 0 , n 就是素数 进一步思考,有必要遍历到 n – 1 吗? 除了1以外,任何合数最小的因子就是2,那最大的因子就是 n/2 那我们就遍历到 n/2就足够了
这样我们就可以写出这个算法的核心代码:
intisPrime(inttarget){
inti=0;
if(target