Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
题意：找素数，找n以内有多少个素数
筛数法统计
class Solution { public int countPrimes(int n){ if (n == 0 || n == 1 || n == 2) return 0; int[] num = new int [n]; for (int i = 0; i < n; i++) { num[i] = i; } for (int i = 2; i < n; i++) { if (num[i] != 0) { for (int j = 2; j*i < n; j ++) num[j*i] = 0; } } int sum = 0; for (int i = 0; i < n; i++) { if (num[i] != 0) sum ++; } return sum - 1; } }
最快的算法应该是 6n那个，但是我不会，hhaha有兴趣的小伙伴可以自学一下
原文：https://www.cnblogs.com/Moriarty-cx/p/9704231.html