知识点
天道好轮回,没想到我一个大学生还要去学小学的知识点
质数:大于1的整数中,只能被1和本身整除,不能被其他数整除就叫做质数,也可以叫做素数
判断一个数是不是质数:就看它的余数是不是等于0,等于0的话就是质数,否则就不是
举例:2,3,5,7,11,13......
合数:大于1的整数中,除了1和本身整除外,还能被其他数整除,就叫做合数,与质数相对,最小的合数是4
举例:4,6,8,9,10.....
算法详解
这道题是很简单的,质数是针对大于1的整数的,所以先判断是否<2,然后再看看可不可以被2~n个数整除就可以了
优化之后
注意:这个优化的地方一定要完全弄懂,后面的算法会多次用到这个优化
优化:
因为一个数的因数一定是在2~n的范围内成对出现的,所以我们可以枚举较小的内一个i,另一个就是n/i,
随着i的不断增加,x/i会越来越小,如果较小的内一个i大于较大的n/i,说明以后就不会再有成对的出现了,
那这个数就可以说是一个质数,就会跳出循环
java代码
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
while(n-- != 0)
{
int x = in.nextInt();
System.out.println(is_prim(x));
}
}
private static String is_prim(int n)
{
if(n < 2) return "No";
for(int i = 2; i <= n / i; i ++)
{
if(n % i == 0) return "No";
}
return "Yes";
}
}