n번째 행운의 숫자를 찾아보세요

행운의 숫자 - 주어진 양의 정수 n에 대해 m > 1인 가장 작은 정수입니다. pn# + m은 소수입니다. 여기서 pn#은 첫 번째 n의 곱 소수입니다.

예를 들어 세 번째 행운의 숫자를 계산하려면 먼저 처음 3개의 소수(2, 3, 5)의 곱인 30을 계산하세요. 2를 더하면 짝수인 32가 되고, 3을 더하면 3의 배수인 33이 됩니다. 최대 6까지의 정수도 제외될 수 있습니다. 7을 더하면 37이 되는데, 이는 소수이다. 따라서 7은 세 번째 행운의 숫자입니다.

첫 번째 원시 숫자의 행운의 숫자는 -

입니다.

3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109….

문제 설명

숫자 n이 주어졌습니다. n번째 행운의 숫자를 찾아보세요.

예 1

으아악 으아악

설명 - 처음 3개 가격 수치의 제품 -

으아악

예 2

으아악 으아악

설명 - 처음 7개 소수의 곱 -

으아악

방법 1: 기존 방법

이 문제를 해결하는 간단한 방법은 먼저 처음 n 소수의 곱인 pn#을 계산한 후 pn#과 다음 소수의 차이를 구하는 것입니다. 얻은 차이는 행운의 숫자가 될 것입니다.

의사코드

으아악

예: C++ 구현

아래 프로그램에서는 처음 n개의 소수와 프리미티브를 찾은 후 다음 소수의 프리미티브를 계산하여 행운의 숫자를 계산합니다. 행운의 숫자는 다음 소수와 원시 숫자의 차이입니다.

으아악

출력

으아악

시간 복잡도 - O(nsqrt(n)), 여기서 prime() 함수의 복잡도는 O(sqrt(n))이고 nthFortunate()의 for 루프의 복잡도는 O(nsqrt(n))입니다.

공간 복잡성 - O(1)

방법 2: 에라토스테네스의 체

에라토스테네스의 체는 모든 소수를 극한까지 가져오는 데 사용되며, 이는 우리에게 MAX 값을 제공합니다. 이 방법에서는 모든 true 항목을 포함하는 부울 배열을 만들고 프라임이 아닌 모든 인덱스를 false로 표시합니다. 그런 다음 배열의 처음 n 소수를 곱하여 처음 n 소수의 곱을 구합니다. 그런 다음 이전 방법과 유사하게 2에서 시작하여 곱에 1을 추가하여 다음 소수를 얻습니다. 다음 소수와 상품의 차이가 필요한 행운의 숫자입니다.

의사코드

으아악

예: C++ 구현

다음 프로그램에서 MAX 크기의 부울 소수 배열은 MAX 이전의 모든 소수를 기록합니다. 그런 다음 처음 n개의 소수를 곱하여 원본을 찾습니다. 그런 다음 이전 방법과 유사하게 nextPrime을 찾습니다. nextPrime과 Product의 차이는 행운의 숫자입니다.

으아악

출력

으아악

시간 복잡도 - O(n log(log(n)))

공간 복잡도 - O(MAX)

결론

결론적으로 n번째 행운의 숫자는 다음 두 가지 방법으로 찾을 수 있습니다.

기본 방법: 처음 n 소수의 곱을 찾고 그 곱을 기준으로 다음 소수를 계산합니다. 소수와 상품의 차이가 n번째 행운의 숫자입니다.

에라토스테네스의 체: 특정 한계에 도달하는 모든 소수를 찾은 후 다음 소수로 곱을 계산하여 행운의 숫자를 찾습니다.

두 방법 모두 가변 크기 제약으로 인해 더 작은 n 값에 효율적입니다. 더 큰 가치를 위해서는 더 효율적이고 최적화된 솔루션이 필요합니다.

위 내용은 n번째 행운의 숫자를 찾아보세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!