admin
文章目录
作业标题一、常规方法（最低效）思路说明：缺点：
二、稍微高效的方法（x/2）思路说明：缺点：
三、高效方法（根号x）思路说明：
作业标题
给定一个数字，判定一个数字是否是素数。 素数又叫质数，质数是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。最小的质数是2，它也是唯一的偶数质数，最前面的质数依次排列为：2、3、5、7、11、13、17、19、23、29、31等。 第一种方法是我自己做作业时想到的，但是随着只是不断深入，我们还是要尽可能的将每个解法做到高效。
一、常规方法（最低效）
思路说明：
从而开始，一旦出现能整除的，就表示不是素数，如果从二开始到她本身之前都没有整除的，说明就是素数，这一解法从数组本身的定义出发的。
缺点：
当数字较大时，循环次数太多，所以不建议使用。
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int i=0;
for(i=2;i if(a%i==0){ break; } } if(i==a){ System.out.println(a+"是素数"); }else{ System.out.println(a+"不是素数"); } sc.close(); } 运行结果： 二、稍微高效的方法（x/2） 思路说明： 将循环范围定在2到指定数的二分之一（原理：任何一个数的最大因数都小于等于它的二分之一，所以只要从2查找到x/2，如果都没有被整除就是素数，因为到这里已经查找到他的最大因数了。例如24的最大因数为12，100的最大因数为50.）这样就会减少循环次数。 缺点： 效率提高了不少，但也并不是最优解。 代码如下（示例）： public static void isPrime2(int x){ boolean flag; int i=0; int j=0; flag=true; for(j=2;j<=x/2;j++){ if(x%j==0){ flag=false; break; } } if(j>x/2){ System.out.println("是素数"); }else{ System.out.println("不是素数"); } } public static void main(String[] args) { isPrime2(17); } 三、高效方法（根号x） 思路说明： 其实只要把循环一直从2尝试到根号x就可以，不难发现，一个数的两个因数中，毕然有一个小于等于根号x，一个大于等于根号x，例如100的因数有：1和100，2和50，4和25，5和20，10和10.所以只要从2尝试到根号x，如果都没有被整除，就是素数，否则就不是。和第二种方法类似，但是效率相对更高，推荐使用。 public static void isPrime1(int x){ boolean flag; int i=0; int j=0; flag=true; for(j=2;j<=Math.sqrt(x);j++){ if(x%j==0){ flag=false; break; } } if(j>Math.sqrt(x)){ System.out.println("是素数"); }else{ System.out.println("不是素数"); } } public static void main(String[] args) { isPrime1(17); }