범위에서 소수 계산

난이도 중급
자주 묻는 질문 구글 인상 쿨리 자 체 Snapchat Yahoo
수학 넘버 시스템조회수 43
링크드 인버퍼레딧텀블러

문제 정책

"범위 내 소수 계수"문제는 범위 [왼쪽, 오른쪽]이 주어 졌음을 나타냅니다. 여기서 0 <= left <= right <= 10000입니다. 문제 설명은 범위 내의 총 소수 수를 알아 내도록 요청합니다. 많은 수의 쿼리가 있다고 가정합니다.

예

left: 4
right:10
2

설명

5와 7은 유일한 2 개의 소수입니다.

범위에서 소수 계산핀

left: 6
right:8
1

설명

7은 유일한 소수입니다.

암호알고리즘

  1. 를 생성 정수 배열 및 부울 배열 '초기' 주어진 최대 크기를 지정하고 다음으로 부울 배열을 초기화합니다. 참된.
  2. 부울 배열을 탐색하고 'prime'배열의 현재 값이 참인지 확인합니다.
  3. 그런 다음 현재 배열 요소에서 순회를 시작하고 그때부터 각 배열 요소를 현재 요소의 크기와 동일한 거리에있는 false로 초기화합니다. 이것은 현재 요소의 배수로 이동하고 있음을 의미합니다.
  4. prePrime [0] 및 prePrime [1]을 0으로 설정합니다.
  5. 2에서 주어진 최대 값까지 이동합니다.
  6. 값을 prePrime 배열의 이전 인덱스에 복사하고 프라임 배열의 현재 값이 true인지 확인한 다음 prePrime 값의 값을 1 씩 늘립니다.
  7. 각 쿼리에 대해 prePrime [right] 및 prePrime [left-1]의 차이를 반환합니다.

설명

숫자 범위를 시작 번호와 끝 번호로 지정합니다. 따라서이 범위는 모든 중간 숫자로 채워져 있으므로 고려하십시오. 우리는이 범위 내에서 소수의 총 수를 알아 내도록 요청했습니다. 이를 위해 최대 개수 범위 내에서 모든 쿼리를 해결할 수있는 prePrime 배열을 구축 할 것입니다. 우리에게 주어진 최대 크기 10000의 정수 배열을 선언하고 동일한 크기로 true 값으로 초기화 한 Boolean 배열을 선언합니다.

XNUMX을 소수로 간주 할 수 없기 때문에 값 XNUMX에서 루프를 순회합니다. 부울 소수 배열의 각 값이 참인지 확인하고, 참이면 루프에서 더 이동합니다. 현재 숫자의 두 배에서 시작하여 최대 크기 값에 도달 할 때까지 배수로 이동하고 그때부터 각 값을 false로 초기화합니다. 이 접근 방식은 일반적으로 에라토스테네스의 체.

값을 0으로 설정합니다.th 및 1st prePrime 배열의 값을 0으로 설정합니다. 2부터 시작하여 prePrime 및 prime 배열을 순회합니다. 그런 다음 prePrime 배열의 다음 값을 prePrime 배열의 이전 값에 복사하고 프라임 배열의 현재 값이 참인지 확인하고 참이면 prePrime 배열의 현재 요소 값을 늘립니다. 각 쿼리에 대해 시작 번호와 끝 번호로 수신됩니다. prePrime [right]와 prePrime [left-1]의 차이를 반환합니다. 그것이 필수 답변이 될 것입니다.

암호

범위에서 소수를 계산하기위한 C ++ 구현

#include<iostream>
#include<stdio.h>
#include<cstring>

using namespace std;

const int MAX = 10000;

int prePrime[MAX + 1];

void PrePrimeFunction ()
{

    bool prime[MAX + 1];
    memset(prime, true, sizeof(prime));

    for (int a = 2; a * a <= MAX; a ++)
    {
        if (prime[a] == true)
        {
            for (int i = a * 2; i <= MAX; i += a)
                prime[i] = false;
        }
    }
    prePrime[0] = prePrime[1] = 0;
    for (int q = 2; q <= MAX; q++)
    {
        prePrime[q] = prePrime[q - 1];
        if (prime[q])
            prePrime[q]++;
    }
}

int solveQuery(int L, int R)
{
    return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
}

int main()
{
    PrePrimeFunction();

    int L = 4, R = 10;
    cout << solveQuery(L, R) << endl;

    L = 6, R = 8;
    cout << solveQuery(L, R) << endl;

    return 0;
}

2
1

범위에서 소수를 계산하기위한 Java 구현

import java.util.Arrays;

class PrimeInRange
{

    static final int MAX = 10000;

    static int prePrime[] = new int[MAX + 1];

    static void PrePrimeFunction()
    {

        boolean prime[] = new boolean[MAX + 1];
        Arrays.fill(prime, true);

        for (int a = 2; a * a <= MAX; a++)
        {
            if (prime[a] == true)
            {

                for (int i = a * 2; i <= MAX; i += a)
                    prime[i] = false;
            }
        }

        prePrime[0] = prePrime[1] = 0;

        for (int q = 2; q <= MAX; q++)
        {
            prePrime[q] = prePrime[q - 1];
            if (prime[q])
                prePrime[q]++;
        }
    }

    static int solveQuery(int L, int R)
    {
        return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
    }

    public static void main(String[] args)
    {
        PrePrimeFunction();
        int L = 4, R = 10;
        System.out.println(solveQuery(L, R));

        L = 6;
        R = 8;
        System.out.println(solveQuery(L, R));
    }
}

2
1

복잡성 분석

시간 복잡성

O (n * log (log (n)) + q) 어디에 "엔" 배열의 요소 수이며 "Q" 쿼리 수입니다. 따라서 이번 복잡성은 "Sieve of Eratosthenes"를 사용한 알고리즘 때문입니다.

공간 복잡성

O (1) 배열의 크기는 입력에 의존하지 않기 때문에 상수 값과 같습니다. 소수의 결과를 저장하려면 공간이 필요하기 때문입니다. 숫자가 소수인지 아닌지 저장하기 때문에.

링크드 인버퍼레딧텀블러
Translate »