유해한 숫자-C++-php.cn

유해한 숫자

WBOY

풀어 주다： 2023-08-26 11:17:15

앞으로

1082명이 탐색했습니다.

유해한 숫자

숫자는 양의 정수이고 이진수 확장에 설정된 자릿수가 소수인 경우 유해한 것으로 간주됩니다. 첫 번째 유해한 숫자는 3 = (11)₂이므로 3입니다. 3의 이진수 표현에는 소수인 2라는 설정된 자릿수가 있음을 알 수 있습니다.

유해한 숫자 10개는 3, 5, 6, 7, 9, 10, 11, 12, 13, 14입니다. 흥미롭게도 2의 거듭제곱은 항상 1비트만 설정하기 때문에 결코 해로운 숫자가 될 수 없습니다. 1은 소수가 아닙니다. 반면에 n이 자연수인 2ⁿ + 1로 표현될 수 있는 모든 숫자는 2개의 세트 비트를 가지며 2가 소수라는 것을 알고 있기 때문에 항상 잘못된 숫자입니다.

이러한 유해한 숫자의 속성을 염두에 두고 다음 기사에서는 숫자가 유해한지 확인하는 방법을 설명합니다.

문제 설명

이 질문은 주어진 숫자 n이 유해한 숫자인지 확인하는 것을 목표로 합니다. 즉, 이진 확장에서 설정된 비트의 소수를 갖는 양수인지 확인하는 것입니다.

예

으아아아 으아아아

Explanation

의 번역은 다음과 같습니다:

Explanation

37 = 100101의 이진 표현.

자릿수 설정 = 3

3은 소수이므로 37은 나쁜 숫자입니다.

으아아아 으아아아

Explanation

의 번역은 다음과 같습니다:

Explanation

22 = 10110의 이진 표현.

자릿수 = 3으로 설정하세요.

3은 소수이므로 22는 악의수입니다.

으아아아 으아아아

Explanation

의 번역은 다음과 같습니다:

Explanation

71의 이진 표현은 1000111입니다.

자릿수 = 4로 설정합니다.

4는 소수가 아니므로 71도 나쁜 숫자는 아닙니다.

으아아아 으아아아

Explanation

의 번역은 다음과 같습니다:

Explanation

64의 이진 표현은 1000000입니다.

자릿수 = 1로 설정합니다.

64 = 2⁶이므로 2의 거듭제곱이므로 1세트 비트를 갖습니다. 1은 소수가 아니므로 64는 악수가 아닙니다.

솔루션

숫자가 악성인지 판단하기 위해서는 설정된 자릿수가 소수인지 여부를 알아야 합니다. 주요 작업은 이 숫자의 이진 확장에서 설정된 자릿수를 계산하는 것입니다. 다음 방법을 사용하여 설정된 자릿수를 계산한 다음 그 결과가 소수인지 여부를 확인할 수 있습니다.

방법에는 다음 단계가 포함됩니다 -

루프 및 오른쪽 시프트 연산자를 사용하여 숫자의 모든 비트를 반복합니다.
비트 값이 1이면 설정된 비트의 개수가 1 증가합니다.
카운트의 최종 값이 소수인지 확인하세요.
답변을 보여주세요.

알고리즘

함수 is_prime()

if (n

반품 오류

for (i는 2에서 √a까지)

만약 (a%i==0)

반품 오류

참을 반환

함수 count_set_bits()

카운터 초기화 = 0
(n > 0)일 때
if ((n & 1) > 0)
카운터 = 카운터 + 1
n = n >> 1

반품 카운터

함수 is_pernious()

카운터 초기화
카운터 = count_set_bits(n)
if (is_prime(counter) == true)

참을 반환

기타

반품 오류

함수 main()

n 초기화
if (is_pernious())

cout

기타

cout

인쇄물

예: C++ 프로그램

프로그램은

is_pernicious()

함수를 사용하여 숫자가 위험한지 여부를 결정합니다.

count_set_bits()

함수에서 각 반복이 끝날 때 값을 n만큼 오른쪽으로 이동하여 루프의 각 반복에서 최하위 비트를 분석합니다. 그런 다음

is_prime()

함수를 호출하여 설정된 자릿수가 소수인지 여부를 수집합니다.

으아아아

출력

으아아아

시공간 분석

시간 복잡도: O(log(n) + sqrt(count)). count_set_bits() 함수에서 루프는 숫자를 비트 단위로 분석하면서 log(n) 번을 실행합니다. is_prime() 함수는 count가 소수인지 확인하는 데 O(sqrt(count)) 시간이 걸립니다. 두 함수 모두 실행 중에 한 번 호출됩니다.

공간 복잡도: O(1), 구현에 보조 공간이 사용되지 않기 때문입니다. 입력 숫자의 크기에 관계없이 알고리즘은 항상 일정한 양의 공간을 사용합니다.