leetcode 204题

leetcode 204.

题目要求：

Description:

Count the number of prime numbers less than a non-negative number, n.

翻译：统计小于非负数n的素数个数。

输入输出示例：

Input: 100

Output: 25

解题思路：

题目比较简单，素数问题也算是各种问题中常见的问题了。首先要明白的一点是，什么是素数？素数又称为质数，指的是在大于1的自然数中，除了1和它本身外不再有因数的数。

最简单的思路是，尝试用n去除2到n-1，发现有整除，可以确认这不是素数。但是这样很费劲有没有？要统计个数，就要把所有的数都算一遍。

再考虑一下，n的因数不可能大于sqrt（n），那么遍历从n到sqrt（n）就够了。但是这样还是很慢，如果n不大还行，如果n很大，运力的消耗将很严重。

再对素数进行分析，从2到n这中间，仍然会存在很多不靠谱的数字，比如4,6,8等等，他们必然能被2整除，也就是说，凡是2-sqrt（n）的整数倍的数字，那肯定不是素数了。首先把偶数排掉，就去掉了一半的数字，以此类推。

所以，建立一个bool类型的数组，用来标记是素数或者不是素数，长度为n+1.并对它进行初始化，0,1设为false，2,3设为true，从4开始，所有偶数设为false，其他设为true。

然后设置一个i从2到sqrt（n）的循环，仍然跳过偶数。接着内层循环对i的倍数进行标记false，当把sqrt（n）也标记完的时候，整个array就完成了，最后统计一遍true的次数，就可以得到结果了。

不过测试之后发现有个bug，当n很大的时候长度会超出限制，但是我现在想不出更好的方法了，谁能解答一下？欢迎讨论。

Java代码的实现：

public class Solution {

public int countPrimes(int n) {

boolean prime[] = new boolean[n+1];

//initial array 排掉偶数，注意开头几个单元的标注

for(int i = 0; i < n+1; i++)

{

if(i == 0 || i == 1)

prime[i] = false;

else if(i < 4)

prime[i] = true;

else if(i % 2 == 0)

prime[i] = false;

else

prime[i] = true;

}

//标记其他单元

for(int i = 3; i < (int)Math.sqrt(n); i += 2)

for(int j = i + i; j < n + 1; j += i)

{

if(prime[j])

{

prime[j] = false;

}

}

int result = 0;

//统计输出结果

for(int i = 1; i < n+1; i++)

{

if(prime[i])

result++;

}

return result;

}

}