p204

发表于 | 分类于 |

LeetCode p204 Count Primes 题解

1.题目：

Description:

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

题意：

输入n计算小于n的数中有多少个质数。

2.解题思路:

用数组进行储存，见代码。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public class Solution {
    public int countPrimes(int n) {
        int ans = 0;
		boolean p[] = new boolean[n+1];
		for (int i = 2; i < n; i++) {
			if (p[i] == false) {
				ans++;
				for (int j = 2; i * j < n; j++) {
					p[i * j] = true;
				}
			}
		}
		return ans;
    }
}

4.一些总结：