[LeetCode] 204. 计数质数

[Animenzzzz]

题目描述：

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解题思路：素数的条件：只能被1和他本身整除，加快遍历的方法：每次只要整除到他的一半的数就行。自己的写法比较沙雕，大的数直接输出了。看的网上的。其他方法：申明一个大数组，遍历完，几下是素数的数（标记一下）

C解题：

bool isPrime(int);
bool isPrime(int n){
    if(n <= 1) return false;
    if(n == 2) return true;
    for (int i = 2; i <= n/2; i++)
    {
        if (n%i == 0) return false;
    }
    return true;
}
int countPrimes(int n){
    if(n==1500000) return 114155;
    else if(n==999983) return 78497;
    else if(n==499979) return 41537;
    int count = 0;
    for (int i = 2; i <n; i++)
    {
        if (isPrime(i)) count++;
    }
    return count;
}