美文网首页
204. Count Primes

204. Count Primes

作者: YellowLayne | 来源:发表于2017-06-27 09:48 被阅读0次

    1.描述

    Description:

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

    2.分析

    3.代码

    int countPrimes(int n) {
        if (n <= 1) return 0;
        bool *isPrime = (bool*)malloc(n * sizeof(bool));
        for (unsigned int i = 0 ; i < n; ++i)
            isPrime[i] = true;
        int root = sqrt(n);
        for (unsigned int i = 2; i <= root; ++i) {
            if (isPrime[i]) {
                for (unsigned int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int sum = 0;
        for (unsigned int i = 2; i < n; ++i) {
            if (isPrime[i]) ++sum;
        }
        free(isPrime);
        isPrime = NULL;
        return sum;
    }
    

    相关文章

      网友评论

          本文标题:204. Count Primes

          本文链接:https://www.haomeiwen.com/subject/csiscxtx.html