逆向思维求解质数 - JAVA

质数即大于1的一个自然数，这个数可以被1和自身整除，如算出100之内的质数，它们有2，3，5，7，11，13，17，19...这样的数字。这道题也是面试过程中笔试常问的一道题。

普通青年正向求解：

public static void main(String[] args) {  
        ArrayList zhishu = new ArrayList();  
  
        for (int n = 3; n < 100; n = n + 2) {  
            boolean flag = false;  
            for (Integer itger : zhishu) {  
                if (n % itger == 0) {  
                    flag = true;  
                    break;  
                }  
            }  
  
            if (!flag) {  
                zhishu.add(n);  
            }  
        }  
  
        System.out.println(zhishu);  
}

文艺青年逆向求解：

public static void main(String[] args) {  
        int n = 100;  
        int[] array = new int[n];  
  
        for (int i = 2; i < n; i++) {  
            array[i] = i;  
        }  
  
        for (int i = 2; i < n; i++) {  
            if (array[i] != 0) {  
                int j, temp;  
                temp = array[i];  
                for (j = 2 * temp; j < n; j = j + temp) {  
                    array[j] = 0;  
                }  
                System.out.println(array[i]);  
            }  
        }  
}