자바 - 구 질 수 (엘 라 토 세 니 의 소수 체 법 등 여러 가지 방법)

package com.zth;
/**
 * 求小于 x 的所有质数
 * @author 时光·漫步
 *
 */
public class ZhiShu {
  // 方法一：遍历
  public static int  fun1(int x) {
    if(x<2) {
      return 0;
    }
    if(x == 2) {
      return 1;
    }
    for(int i = 2;i< x;i++) {
      if(x%i == 0) {
        return 0;
      }
    }
     return 1;
  }

  
  //x 如果有（除了自身以外的）质因数，则小于等于 x/2
  public static int  fun2(int x) {
    if(x<2) {
      return 0;
    }
    if(x == 2) {
      return 1;
    }
    for(int i = 2;i<= x/2;i++) {
      if(x%i == 0) {
        return 0;
      }
    }
     return 1;
  }
  
  //除了0和2以外的偶数都不是素数
  public static int  fun3(int x) {
    if(x == 2) {
      return 1;
    }
    if(x<2 || x%2==0 )
      return 0;
    
    for(int i = 3;i<= x/2;i += 2) {
      if(x%i == 0) {
        return 0;
      }
    }
     return 1;
  }
  
    //对于一个小于n的整数X，如果n不能整除X,则n必定不能整除n/X。反之相同

    //一个明显的优化，就是只要从2枚举到√n 即可。

    // 因为在判断2的同时也判断了n/2。到√n时就把2到n-1都判断过了。
  
  public static int  fun4(int x) {
    if(x == 2) {
      return 1;
    }
    if(x<2 || x%2==0 )
      return 0;
    double  n = Math.sqrt(x);
    for(int i = 3;i<= n;i += 2) {
      if(x%i == 0) {
        return 0;
      }
    }
     return 1;
  }
  
  //埃拉托色尼的素数筛法
  public static void   fun5(int x) {
    
    boolean[] arr = new boolean[x+1];
    // 初始化数组为 true
    for(int i = 0 ;i

실행 결과:

方法一结果：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

方法二结果：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

方法三结果：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

方法四结果：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

方法五结果：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97