import java.util.ArrayList;
import java.util.List;

public class Ch4_1_2 {
    public static void main(String[] args)
    {
        System.out.println("100以内的素数如下：");
        List<Integer> lists = getPrimes(100);
        for(int i = 0;i < lists.size();i++)
        {
            Integer list = lists.get(i);
            System.out.print(list+" ");
            if(i % 10 == 0)
                System.out.println();
        }
    }
    /** * 求n以内的所有素数 * @param n 范围 * @return n以内的素数 */
    private static List<Integer> getPrimes(int n)
    {
        List<Integer> result = new ArrayList() ;
        result.add(2);
        for(int i=3;i<=n;i+=2)
        {
            if(!divisible(i,result))
            {
                result.add(i);
            }
        }
        return result;
    }

    private static boolean divisible(int n, List<Integer> primes) {
        for(Integer prime : primes)
        {
            if(n % prime == 0)
            {
                return true;       //整除，则返回真
            }
            if(prime >= Math.sqrt(n) )   //如果超过平方根还没有整除，则退出循环
                break;
        }
        return false;
    }
}