题目描述
编程求2∼n(n为大于2的正整数)中有多少个素数。
提示
质数又称素数（prime number）。是指一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。
埃氏筛法(素数筛) --目前找素数最快的方法
埃式筛法：给定一个正整数n(n<=106)，问n以内有多少个素数？
做法：首先将2到n范围内的整数写下来，其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是O(nlogn)。