java 代码求质数

质数概念：质数，又称素数，指在一个大于1的[自然数]中，除了1和此整数自身外，无法被其他自然数[整除]的数（也可定义为只有1和本身两个[因数]的数）。最小的素数是2，也是素数中唯一的[偶数]；其他素数都是[奇数]。质数有无限多个，所以不存在最大的质数。

 public static void main(String[] args) {
        // 求100以内的质数

        for (int i = 2; i <= 100; i++) { // 质数
            for (int k = 2; k <= i; k++) { // 除数
                // 排除所有在 i=k 之前 能被k整除(余数为0)的数
                if (i % k == 0 && i != k) {
                    break;
                }
                // 输出所有在 i=k 且 i%k=0的数
                if (i % k == 0 && i == k) {
                    System.out.println(i);
                }
            }
        }
    }

1：根据定义去求解：也是最笨的方式，效率比较低

 public static void main(String[] args) {
         printPrime(1000);
    }
    public static void  printPrime(int n){
         
        for(int i = 2; i < n ; i++){
             
            int count = 0;
             
            for(int j = 2 ; j<=i; j++){
                 
                if(i%j==0){
                    count++;
                }
                if(j==i & count == 1){
                    System.out.print(i+" ");
                }
                if(count > 1){
                    break;
                }
            } 
        }
    }

2：平方根

public static void main(String[] args) {
         
        for(int j = 2; j<1000; j++){
            if(m(j)){
                System.out.print(j+" ");
            }
        }
    } 
public static boolean  m(int num){
     
        for(int j = 2; j<=Math.sqrt(num);j++){
            if(num%j == 0){
                return false;
            }
        }
        return true;
    }

3：找规律（摘自一个论坛讨论）
最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。第三种方法说明了一个质数的特性：在所有质数中，只有2是偶数。
如果一个数能够被它之前的质数整除，那么这个数不是质数。

public class Primes {
          
      public static void main(String[] args) {
         
        // 求素数
        List<Integer> primes = getPrimes(1000);
      
        // 输出结果
        for (int i = 0; i < primes.size(); i++) {
          Integer prime = primes.get(i);
          System.out.printf("%8d", prime);
          if (i % 10 == 9) {
            System.out.println();
          }
        }
      }
      
      /**
       * 求 n 以内的所有素数
       * @param n 范围
       * @return n 以内的所有素数
       */
      private static List<Integer> getPrimes(int n) {
        List<Integer> result = new ArrayList<Integer>();
        result.add(2);
        for (int i = 3; i <= n; i += 2) {
          if (!divisible(i, result)) {
            result.add(i);
          }
        }
        return result;
      }
      
      /**
       * 判断 n 是否能被整除
       * @param n   要判断的数字
       * @param primes 包含素数的列表
       * @return 如果 n 能被 primes 中任何一个整除，则返回 true。
       */
      private static boolean divisible(int n, List<Integer> primes) {
        for (Integer prime : primes) {
          if (n % prime == 0) {
            return true;
          }
        }
        return false;
      }
    }

4.while循环

public static void main(String[] args) {
  int i,n,k=0;
     for (n = 3; n<=100; n++) {     //3~100的所有数
         i=2;
       while (i<n) {
             if (n%i==0) 
                break;  //若能整除说明n不是素数，跳出当前循环
             i++;
          }
      if (i==n) {     //如果i==n则说明n不能被2~n-1整除，是素数
             k++;             //统计输出数的个数
             System.out.print(i+ "\t ");
             if (k %6==0)    //每输出5个则换行
              System.out.println();
         }
     }
 }