유해한 숫자
- WBOY앞으로
- 2023-08-26 11:17:151093검색
숫자는 양의 정수이고 이진수 확장에 설정된 자릿수가 소수인 경우 유해한 것으로 간주됩니다. 첫 번째 유해한 숫자는 3 = (11)2이므로 3입니다. 3의 이진수 표현에는 소수인 2라는 설정된 자릿수가 있음을 알 수 있습니다.
유해한 숫자 10개는 3, 5, 6, 7, 9, 10, 11, 12, 13, 14입니다. 흥미롭게도 2의 거듭제곱은 항상 1비트만 설정하기 때문에 결코 해로운 숫자가 될 수 없습니다. 1은 소수가 아닙니다. 반면에 n이 자연수인 2n + 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 = 26이므로 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), 구현에 보조 공간이 사용되지 않기 때문입니다. 입력 숫자의 크기에 관계없이 알고리즘은 항상 일정한 양의 공간을 사용합니다.
결론
잘못된 숫자는 흥미로운 수학적 개념이며 위에서 설명한 방법을 사용하여 쉽고 효과적으로 식별할 수 있습니다. 또한 이 문서에서는 사용되는 알고리즘, C++ 프로그램 솔루션, 시간 및 공간 복잡성 분석에 대해 설명합니다.
위 내용은 유해한 숫자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!