easy-algorithm-interview-and-practice/mathcasebycase/埃氏筛法求区间内质数.md

1.判断整数是否为质数

如果要判断某个整数是否为质数，这个相信不是很难。

    public static boolean prime(int n) {
        if (n == 2) {
            return true;
        }

        if (n % 2 == 0) {
            return false;
        }

        for(int i=3; i * i <= n; i+=2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

如果d是n的约数，易知n = d * \frac{n}{d}
因此\frac{n}{d}也是n的约数
并且，这两个数中较小的一个min(d, \frac{n}{d}) <= \sqrt n
因此，我们只需要对前\sqrt n个数进行处理就可以。

2.枚举前n个数中的所有质数

如果不是判断单个数是否为质数，而是枚举前n个数中的所有质数呢？
常见的解法为埃氏筛法。核心思想是枚举从小到大的素数并将素数的整数倍依次从原整数数组中删除，余下的即为全部素数。
wiki百科
有个特别形象的图可以说明

import org.apache.commons.lang3.Validate;

public class Primes {

    public static void test(int n) {
        Validate.isTrue(n > 0);
        int[] nums = new int[n+1];
        for(int i=2; i<=n; i++) {
            for(int j=i*i; j<=n; j+=i) {
                if (nums[j] == 0) {
                    if (j % i == 0) {
                        nums[j] = 1;
                    }
                }
            }
        }
        if (n >= 2) {
            nums[0] = 1;
            nums[1] = 1;
        }
        for(int i=0; i<=n; i++) {
            if (nums[i] == 0) {
                System.out.println(i);
            }
        }
    }

    public static void main(String[] args) {
        int n = 100;
        test(n);
    }
}

上面算法的时间复杂度为\frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \cdots，即n lg(lgn)。