범위의 소수를 계산하는 JavaScript 프로그램

소수는 정확히 두 개의 완전약수가 있는 숫자입니다. 주어진 범위에서 소수의 개수를 찾는 두 가지 방법을 살펴보겠습니다. 첫 번째는 시간 복잡도가 다소 높은 무차별 대입 방식을 사용하는 것입니다. 그런 다음 이 방법을 개선하고 Sieve of Eratosthenes 알고리즘을 채택하여 더 나은 시간 복잡도를 갖도록 하겠습니다. 이 기사에서는 JavaScript 프로그래밍 언어를 사용하여 주어진 범위에서 전체 소수 수를 찾습니다.

폭력법

먼저 이 방법에서는 숫자가 소수인지 아닌지를 찾는 방법을 배우게 됩니다. 두 가지 방법으로 찾을 수 있습니다. 한 가지 방법의 시간 복잡도는 O(N)이고 다른 방법의 시간 복잡도는 O(sqrt(N))입니다.

숫자가 소수인지 확인하는 직접적인 방법

예

먼저 숫자를 얻을 때까지 for 루프를 수행하고 숫자를 나눌 수 있는 숫자를 계산합니다. 숫자를 나눌 수 있는 숫자가 2가 아닌 경우 숫자는 소수가 아닙니다. 숫자는 소수입니다. 코드를 살펴보겠습니다 -

으아악

위 코드에서는 1부터 숫자까지 순회하여 주어진 숫자를 나눌 수 있는 숫자의 범위에서 숫자를 찾고, 주어진 숫자를 몇 개의 숫자로 나눌 수 있는지 구하고, 이를 바탕으로 결과를 출력합니다.

위 코드의 시간 복잡도는 O(N)입니다. 각 숫자가 소수인지 확인하는 데 드는 비용은 O(N*N)이므로 확인하는 좋은 방법이 아닙니다.

수학적 방법

우리는 한 숫자가 다른 숫자를 완전히 나눌 때 몫도 완전 정수라는 것을 알고 있습니다. 즉, 숫자 p를 숫자 q로 나눌 수 있으면 몫은 r, 즉 q * r = p입니다. r은 또한 숫자 p를 몫 q로 나눕니다. 즉, 완전약수는 항상 쌍으로 나온다는 뜻입니다.

예

위의 논의를 통해 N의 제곱근에 대한 나눗셈만 확인하면 매우 짧은 시간에 동일한 결과가 나올 것이라는 결론을 내릴 수 있습니다. 위 메소드의 코드를 살펴보겠습니다 -

으아악

위 코드에서는 for 루프의 범위를 변경하여 이전 코드를 변경했습니다. 이제 N 요소의 첫 번째 제곱근만 확인하고 개수를 2 늘렸기 때문입니다.

위 코드의 시간 복잡도는 O(sqrt(N))입니다. 즉, 이 방법을 사용하여 주어진 범위에 존재하는 소수의 개수를 찾을 수 있다는 의미입니다.

L부터 R까지의 소수의 개수

예

이전에 주어진 코드를 범위에 구현하고 주어진 범위에 있는 소수의 개수를 계산해 보겠습니다. 코드를 구현해 봅시다 -

으아악

위 코드에서는 for 루프를 사용하여 L에서 R까지의 범위를 반복하고, 각 반복마다 현재 숫자가 소수인지 확인합니다. 숫자가 소수이면 개수를 증가시키고 마지막으로 값을 인쇄합니다.

위 코드의 시간 복잡도는 O(N*N)입니다. 여기서 N은 Range의 요소 수입니다.

에라토스테네스 알고리즘 심사

예

에라토스테네스의 체 알고리즘은 매우 효율적으로 작동하며 다른 알고리즘에 비해 O(Nlog(log(N))) 시간 내에 주어진 범위에서 소수의 개수를 찾을 수 있습니다. 체는 O(N) 공간을 차지하지만 시간이 매우 효율적이므로 중요하지 않습니다. 코드를 살펴보고 나서 코드에 대한 설명으로 넘어가겠습니다 -

으아악

위 코드에서는 에라토스테네스의 체 구현을 볼 수 있습니다. 먼저 크기 R을 포함하는 배열을 만든 다음 for 루프를 사용하여 배열을 반복했습니다. 각 반복에 대해 현재 숫자가 1이 아닌 경우 소수가 아니라는 의미이며 그렇지 않으면 소수이며 R보다 작은 모든 숫자가 있습니다. 현재 소수의 배수가 제거됩니다. 그런 다음 0부터 현재 인덱스까지의 소수 카운트를 저장하고 일정한 시간 내에 0부터 R 범위의 모든 쿼리에 대한 답변을 제공할 수 있는 접두사 배열을 만듭니다.

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(N*log(log(N)))이며, 이는 O(N*N) 및 O(N*(sqrt(N)))에 비해 훨씬 좋습니다. 위 코드는 이전 코드에 비해 공간복잡도가 O(N)으로 높습니다.

결론

이 튜토리얼에서는 JavaScript 프로그래밍 언어를 사용하여 주어진 범위에서 소수의 개수를 찾는 방법을 배웠습니다. 소수는 정확히 두 개의 완전약수를 갖는 수입니다. 1은 완전약수가 하나뿐이므로 소수가 아닙니다. 우리는 O(N*N), O(N*sqrt(N)) 및 O(N*log(log(N)))의 시간 복잡도를 갖는 세 가지 방법을 보았습니다. 또한 처음 두 방법의 공간 복잡도는 O(1)이고, 에라토스테네스의 체 방법의 공간 복잡도는 O(N)입니다.

위 내용은 범위의 소수를 계산하는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!