Counts Primes Leetcode解决方案


难度级别 易得奖学金
经常问 亚马逊 Apple Capital One公司 谷歌 微软
哈希 数学

在这个问题中,我们得到一个整数N。目标是计算小于N的数字是素数。 整数被约束为非负数。

使用案列

7
3
10
4

说明

小于10的质数是2、3、5和7。因此,计数为4。

接近(强力)

通用方法是检查每个小于N的整数,如果它们是质数则递增结果。 例如,假设N =10。现在,我们可以从2到N – 1进行检查,以找出在此范围内有多少个素数。 但是,这种方法需要对整个范围进行初步检查, [2,N – 1]。  因此,这很慢。

我们可以做一些优化,例如:

  1. 除2以外的每个素数都是一个奇数整数。 所以,之后 2, 我们只能检查奇数整数。
  2. 我们可以检查数字是否为素数 O(√N) 是时候改进算法了。

但是,我们仍然有一种更好的方法,本文稍后将进行讨论。

算法

  1. 如果数量小于 3, 返回 0, 因为2是最小的素数
  2. 循环检查所有数字,从3开始
  3. 一个数字,如果满足以下条件,则N为质数:
    • 它也有 介于2和之间的素数 √N
  4. 如果数字是素数,则结果递增
  5. 打印结果

Count Primes Leetcode解决方案的实施

C ++程序

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int N)
{
    for(int i = 2 ; i * i <= N ; i++)
        if(N % i == 0)
            return false;
    return true;
}


int countPrimes(int N)
{
    if(N < 3)
        return 0;
    int cnt = 1;
    for(int i = 3 ; i < N ; i += 2)
        if(isPrime(i))
            cnt++;

    return cnt;
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

Java程序

class count_primes
{
    static boolean isPrime(int N)
    {
        for(int i = 2 ; i * i <= N ; i++)
            if(N % i == 0)
                return false;

        return true;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        int cnt = 1;//since number is atleast 3, 2 is a prime less than N
        for(int i = 3 ; i < N ; i += 2)
            if(isPrime(i))
                cnt++;
        return cnt;
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

Count Primes Leetcode解决方案的复杂性分析

时间复杂度

我们为 N / 2 时代。 在每次检查中,复杂度为O(N / 2)的时间(取平均值为 数 / 2)花费了。 因此,该算法的时间复杂度为 O(N√N)。

空间复杂度

O(1),仅常量空间用于常量变量。

方法(最佳方法)

考虑任何素数,可以说 5, 然后确保5的所有倍数(除自身以外)永远不会是质数,因为它们会将5作为其质数之一。 同样,我们可以存储所有小于N且大于 0

热带地区的 Eratosthenes筛 是一种古老而有效的算法,用于在以下情况下找到小于N的素数 N足够小以分配O(N) 内存中的空间。 通过将所有非素数标记为复合数来迭代消除所有非素数。 标记所有复合材料后,未标记的数字为质数。

另外,我们需要存储一个布尔值 排列 检查是否标记了任何数字,这说明内存使用情况。 因此,在这种情况下,我们 贸易记忆准时改善.

Counts Primes Leetcode解决方案

算法

  1. 维护一个布尔数组 总理 大小等于 N – 1
  2. 主要的[] 用于标记复合材料并在最后检查质数
  3. 将每个整数的素数初始化为 true。 算法集 false 到每个非素数
  4. 运行一个连续的整数循环,从2开始,直到整数的第一个倍数为 小于N:
    • 对于每个整数x,如果其prime [x]为true,则将其所有倍数标记为 false
    • 每个整数的倍数从此处开始 x * x 因为x的所有其他倍数都将被取消标记。
  5. 最后检查[2,N – 1]范围内有多少个数字 true 在主要表中
  6. 打印结果

Count Primes Leetcode解决方案的实施

C ++程序

#include <bits/stdc++.h>
using namespace std;

int sieve(int N)
{
    if(N < 3)
        return 0;

    int cnt = 0;
    bool prime[N];
    for(int i = 2 ; i < N ; i++)
        prime[i] = true;

    for(int i = 2 ; i * i < N ; i++)
    {
        if(prime[i])
            for(int j = i * i ; j < N ; j += i)
                prime[j] = false;
    }

    for(int i = 2 ; i < N ; i++)
        if(prime[i])
            cnt++;

    return cnt;
}

int countPrimes(int N)
{
    if(N < 3)
        return 0;
    return sieve(N);
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

Java程序

class count_primes
{
    static int sieve(int N)
    {
        if(N < 3)
            return 0;

        int cnt = 0;
        boolean[] prime= new boolean[N];
        for(int i = 2 ; i < N ; i++)
            prime[i] = true;

        for(int i = 2 ; i * i < N ; i++)
        {
            if(prime[i])
                for(int j = i * i ; j < N ; j += i)
                    prime[j] = false;
        }

        for(int i = 2 ; i < N ; i++)
            if(prime[i])
                cnt++;

        return cnt;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        return sieve(N);
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

Count Primes Leetcode解决方案的复杂性分析

时间复杂度

该算法的复杂度是 O(Nlog(logN))。 这可以证明为:

对于每个整数X,我们花费时间为 N / X 消除其所有倍数。

因此,总共花费的时间为:N / 2 + N / 3 + N / 5 + N / 7 +……

以N为共同点 T(N)= N(1/2 + 1/3 + 1/5 + 1/7 +…)。 系列的总和(1/2 + 1/3 + 1/5 + 1/7 +…)可以证明为 log(logN)。

因此, T(N)= Nlog(logN)

空间复杂度

上),因为我们创建了一个哈希表来存储数字是否为质数。