카운트 프라임 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 아마존 Apple 자본 하나 구글 Microsoft
알고리즘 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 수학조회수 101

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

이 문제에서는 정수 N이 주어집니다. 목표는 N보다 작은 숫자가 소수인지 계산하는 것입니다. 정수는 음수가 아니도록 제한됩니다.

7
3
10
4

설명

10 미만의 소수는 2, 3, 5 및 7입니다. 따라서 개수는 4입니다.

접근 (Brute Force)

일반적인 접근 방식은 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';
}

자바 프로그램

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

카운트 프라임 Leetcode 솔루션의 복잡성 분석

시간 복잡성

루프를 실행합니다. N / 2 타임스. 모든 검사에서 복잡한 시간 O (N / 2) (평균을 아니오 / 2)이 소비됩니다. 따라서이 알고리즘의 시간 복잡도는 O (N√N).

공간 복잡성

O (1), 상수 변수에는 상수 공간 만 사용됩니다.

접근 방식 (최적 방법)

소수를 고려하십시오. 5, 그런 다음 5의 배수는 모두 5를 소인수 중 하나로 가질 수 있기 때문에 그 자체를 제외한 모든 배수가 절대 소수가 될 수 없습니다. 마찬가지로 N보다 작고 다음보다 큰 모든 숫자를 저장할 수 있습니다. 0

또한 에라토스테네스의 체 N보다 작은 소수를 찾는 고대의 효율적인 알고리즘입니다. N은 O (N)을 할당하기에 충분히 작습니다. 메모리 공간. 소수가 아닌 모든 숫자를 복합으로 표시하여 반복적으로 제거합니다. 모든 합성물이 표시되면 표시되지 않은 숫자가 소수입니다.

또한 부울을 저장해야합니다. 정렬 메모리 사용량을 설명하는 숫자가 표시되어 있는지 확인합니다. 그래서 이것은 우리가 트레이드 메모리 떨어져 제 시간에 개선.

카운트 프라임 Leetcode 솔루션

암호알고리즘

  1. 부울 배열 유지 프라임 다음과 같은 크기 N – 1
  2. 초기[] 합성물을 표시하고 마지막에 프라임을 확인하는 데 사용됩니다
  3. 모든 정수의 소수를 다음과 같이 초기화하십시오. 참된. 알고리즘 세트 그릇된 모든 비 프라임 번호에
  4. 2부터 시작하여 정수의 첫 배수가 될 때까지 연속 정수 루프를 실행합니다. N 미만 :
    • 모든 정수 x에 대해 prime [x]가 true이면 모든 배수를 다음과 같이 표시합니다. 그릇된
    • 여기에있는 모든 정수의 배수는 엑스 * 엑스 x의 다른 모든 배수는 이미 표시가 해제되어 있습니다.
  5. 마지막으로 [2, N – 1] 범위에서 몇 개의 숫자가 있는지 확인하십시오. 참된 프라임 테이블에서
  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';
}

자바 프로그램

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

카운트 프라임 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)

공간 복잡성

의 위에), 숫자가 소수인지 아닌지 저장할 해시 테이블을 생성합니다.

균열 시스템 설계 인터뷰
Translate »
1