주어진 이진수를 L과 R 사이의 밑수로 변환한 후 소수의 개수를 계산하세요.-C++-php.cn

주어진 이진수를 L과 R 사이의 밑수로 변환한 후 소수의 개수를 계산하세요.

PHPz

풀어 주다： 2023-09-06 13:25:06

앞으로

562명이 탐색했습니다.

주어진 이진수를 L과 R 사이의 밑수로 변환한 후 소수의 개수를 계산하세요.

제목 '주어진 이진수를 L과 R 사이에 변환한 후 소수의 개수'라는 제목은 L과 R 사이의 이진수를 밑수로 변환한 후 L과 R 사이의 숫자를 세는 수학 문제를 의미합니다. 소수의 수입니다. 전환하다. 수학에서 소수는 1과 자기 자신으로만 나누어지는 1보다 큰 정수입니다.

이진수를 다른 진수의 숫자로 변환하려면 다른 숫자 체계로 숫자를 써야 합니다. 숫자 체계의 기본은 고유한 숫자의 수이며 변환은 새 기본에서 해당 숫자의 동등한 표현을 찾아 수행됩니다. 변환 후 소수를 계산하는 것은 암호학, 컴퓨터 과학 및 기타 분야에서 사용되는 어려운 정수론 문제입니다. 이 문제를 해결하려면 정수론, 소수, 정수 체계에 대해 많이 알아야 합니다.

소수란 무엇인가요?

숫자는 1과 숫자 자체로 나누어지는 경우에만 소수라고 합니다. 예를 들어, 숫자 5는 1과 5로만 나누어지기 때문에 소수이지만, 6은 2와 3으로도 나누어지기 때문에 소수가 아닙니다.

소수 개수는 단순히 주어진 숫자 집합에 소수가 몇 개 있는지 묻는 것입니다. 예를 들어, 숫자 집합 {1,2,3,4,5,6,7,8,9}을 생각해 보세요. 이 숫자 집합에서 소수의 개수는 4이고 2, 3, 5입니다. , 그리고 7. 게다가 1은 유일한 양의 인수가 1 그 자체이기 때문에 소수가 아닙니다.

방법

소수 문제를 계산하는 방법에는 아래와 같이 두 가지 주요 방법이 있습니다 −

폭력적인 방법
소인수 분해

알고리즘

1단계 - 이진수와 밑수 L과 R의 범위를 입력하세요.

2단계 - L과 R(포함) 사이의 모든 기준을 반복합니다.

3단계 - 이진수를 현재 진수로 변환합니다.

4단계 − 변환된 숫자가 소수인지 확인하세요.

5단계 - 변환된 숫자가 소수인 경우 소수 개수를 1씩 늘립니다.

6단계 - L~R 범위의 모든 염기에 대해 3~5단계를 반복합니다.

7단계 − 얻은 소수의 총 개수를 반환합니다.

아래는 알고리즘의 의사코드입니다 -

으아악

number_is_prime()은 숫자를 입력으로 받아들이고 숫자가 소수인지 여부를 나타내는 부울 값을 반환하는 메서드입니다.

방법 1: 폭력적인 해결

무차별 접근 방식에는 이진수를 L에서 R까지의 각 진수로 변환하고 각 변환에서 소수의 수를 계산하는 작업이 포함됩니다. 숫자가 더 클 경우 가능한 모든 변형을 확인해야 하므로 시간이 많이 걸릴 수 있습니다.

아래 코드에는 세 가지 기능이 포함되어 있습니다. 첫 번째 함수는 입력 숫자가 소수이면 1을 반환하고 그렇지 않으면 0을 반환하는 "isPrime"입니다. 두 번째 함수 "binaryToDecimal"은 이진수를 십진수로 변환합니다. 세 번째 함수 "countPrimes"는 입력 범위 사이의 이진수를 십진수로 변환하여 얻은 소수의 개수를 셉니다. 마지막으로, 메인 함수는 이진수와 숫자 범위를 받아 "countPrimes" 함수를 호출하고 소수의 개수를 인쇄합니다.

Example

의 중국어 번역은

Example

입니다.

이 코드는 이진수와 L 및 R 범위에 대해 미리 정의된 값을 제공합니다. 이 예에서는 이진수 1010과 범위 5~20을 사용했습니다. 필요에 따라 기본 기능에서 이러한 값을 변경할 수 있습니다.

으아악

출력

으아악

방법 2: 소인수분해

소인수 분해에는 변환된 숫자의 소인수를 찾고 소인수 범위 내에 있는지 확인하는 작업이 포함됩니다. 이는 더 작은 수의 경우 효율적인 방법일 수 있지만 더 큰 수의 경우 계산 비용이 많이 들 수 있습니다.

아래 코드는 주어진 숫자가 소수인지 확인하거나 주어진 숫자 앞에 있는 소수의 수를 계산하는 두 가지 함수 isPrime() 및 countPrimes()를 정의합니다. 메인 함수는 사용자가 입력한 이진수와 기수 제한을 받아들이고, 이진수를 십진수로 변환한 다음, 주어진 제한 내에서 다른 기수로 변환합니다. 각 변환에 대해 프로그램은 소인수를 찾고, 소인수가 현재 기본 한도 내에 있으면 카운터를 증가시킵니다. 마지막으로 프로그램은 발견된 소수의 개수를 인쇄합니다. 코드는 표준 입력/출력 및 부울 라이브러리를 가져옵니다.