java求素数的两种方法

求200-500之间所有素数

思想一 试除法

要判断X是否为质数，就从2一直尝试到x-1
做法效率差，可适当修改循环控制条件稍微加强效率

  int count2 = 0;
//  for (int j = 200; j < 500; j++) {
  for (int j = 201; j < 500; j +=2) {
   boolean flag = true;
//   for (int j2 = 2; j2 < j; j2++) {
//    if (j%j2 == 0) {
//     flag = false;
//     break;
//    }
//   }
   for (int j2 = 2; j2 < j/2; j2++) {
    if (j%j2 == 0) {
     flag = false;
     break;
    }
   }
   if (flag) {
    System.out.print(j+" ");
    count2++;
    if (count2 % 8 == 0) {
     System.out.println();
    }
   }
  }
//  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 

思想二 筛选法

该方法思想的百度百科
2是公认最小的质数，先把所有2的倍数去掉；
然后剩下的那些大于2的数里面，最小的是3，3也是质数；
然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是质数5，上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

实现步骤

1. 构造一个定长的标记数组，通常是boolean型，长度是所求范围的最大值+1，于是下标代表该范围的所有数字。（该题若求质数个数 用int数组更简单）
2. 布尔类型默认全是false，也可以不初始化。只需要修改条件。
3. 是当前最小数倍数就被标记。
4. 循环筛选结束后，判断标记数组的值若没被标记，则打印下标。

int[] flag2 = new int[500];//下标与元素相等
  for (int j = 2; j < Math.sqrt(flag2.length); j++) {
   if (flag2[j] == 1) {// 最小的除数是合数 就下一次 
    continue;
   }
   for (int j2 = 3; j2 < flag2.length; j2++) {
    if (flag2[j2] == 1) {//已经标记的就跳过
     continue; 
    }
    if (j2 % j == 0) {//将是j的倍数的数剔除 标记为1
     flag2[j2] = 1;
    }
   }
  }
  int count6 = 0;
  for (int j = 201; j < flag2.length; j +=2) {
   if (flag2[j] == 0) {
    System.out.print(j+" ");
    count6++;
    if (count6 % 8 == 0) {
     System.out.println();
    }
   }
   
  }
  System.out.println();
//  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

本文地址：https://blog.csdn.net/cora_99/article/details/107374326