컴퓨터 프로그래밍의 세계에서는 주어진 범위에서 특정 숫자와 서로소인 숫자의 수를 찾는 것이 일반적인 작업일 수 있습니다. 상대적 소수(relative prime number)라고도 알려진 상대적 소수는 1 외에 공통인수가 없는 숫자입니다. 이번 글에서는 C++ 언어를 사용하여 주어진 정수 L과 R 사이에서 특정 숫자 P에 상대적으로 소수인 숫자의 개수를 찾는 방법을 살펴보겠습니다.
먼저 다음 코드 예제에서 사용할 메소드의 구문을 개략적으로 설명하겠습니다.
으아악우리가 서로소 수의 개수를 계산하는 데 사용할 알고리즘은 다음과 같습니다 −
변수 개수를 0으로 초기화합니다. 이는 서로소 수의 개수를 저장하는 데 사용됩니다.
L부터 R까지 각 숫자를 반복합니다.
각 숫자에 대해 P와 상대적으로 소수인지 확인하세요.
num과 P가 상대적으로 소수인 경우 개수를 1만큼 늘립니다.
count의 최종 값을 반환합니다.
우리가 논의할 첫 번째 방법은 순진한 방법입니다. 유클리드 알고리즘을 사용하여 P와의 동일성을 확인하기 위해 이 방법에서는 지정된 범위 내의 각 숫자를 반복적으로 확인해야 합니다.
countCoprimes 함수는 L(시작 범위 값), R(끝 범위 값) 및 P(P 값)의 세 가지 매개 변수를 허용합니다.
countCoprimes 함수 내에서 변수 count를 0으로 초기화하여 코프라임 개수를 저장합니다.
for 루프는 L에서 R까지 각 숫자 num을 반복합니다.
루프에서 변수 a와 b를 각각 num과 P로 초기화합니다.
while 루프에서 유클리드 알고리즘을 사용하여 모듈러 연산을 반복적으로 교환하고 수행하여 a와 b의 최대 공약수(GCD)를 찾습니다.
GCD(a에 저장됨)가 1이면 num과 P가 서로소라는 의미입니다. 이 경우 count 변수를 증가시킵니다.
모든 숫자를 주의 깊게 반복하고 완료되면 반환하여 카운트 값을 마무리합니다.
주요 기능은 L, R, P 변수에 적절한 값을 신중하게 할당합니다.
그런 다음 제공된 값으로 countCoprimes 함수를 호출하고 결과를 결과 변수에 저장합니다.
마지막으로 L과 R 사이에서 P와 상대적으로 소수인 숫자의 개수인 결과를 표시합니다.
이 전략에는 P의 소인수 분해를 활용하여 L과 R 사이에 있는 서로소 정수의 수를 정확하게 계산하는 것이 포함됩니다.
countCoprimes 함수는 L(시작 범위 값), R(끝 범위 값) 및 P(P 값)의 세 가지 매개 변수를 허용합니다.
P의 소인수를 저장하기 위해 순서가 지정되지 않은 인수 집합을 만듭니다. 임시 변수 tempP를 P로 초기화합니다.
2부터 tempP의 제곱근까지 반복합니다. tempP가 i로 나누어지면, 우리는 요인 집합에 i를 추가하고 tempP가 더 이상 i로 나누어지지 않을 때까지 tempP를 i로 나눕니다.
위 루프 이후 tempP가 1보다 크면 그 자체가 소수라는 의미이므로 인수에 추가해야 합니다.
변수 개수를 0으로 초기화하여 서로소 수의 개수를 저장합니다.
L에서 R까지 각 숫자 num을 반복하고 설정된 인수 중 어떤 인수로 나눌 수 있는지 확인합니다. 가능하다면 비공유(non-coprime) 라벨을 붙입니다.
모든 숫자의 반복이 완료되면 결과 개수가 최종 값으로 반환됩니다. main 함수는 L, R, P를 지정된 값으로 초기화합니다.
그런 다음 제공된 값으로 countCoprimes 함수를 호출하고 결과를 결과 변수에 저장합니다.
마지막으로 L과 R 사이에서 P와 상대적으로 소수인 숫자의 개수인 결과를 표시합니다.
지정된 범위 L-R 내에서 서로소 수를 계산하고 특정 값 P를 만족시키는 것은 프로그래머에게 좋은 과제입니다. 하지만 코드 수준에서 가장 좋은 접근 방식은 무엇입니까? 이 기사의 일부로 우리는 이와 같은 문제를 해결할 때 실질적인 효율성을 제공하는 두 가지 C++ 사용 사례에 대해 자세히 살펴봅니다. 첫째, 목표 간격 내의 모든 값을 반복하고 유클리드 알고리즘을 사용하여 숫자가 서로 일치하는지 확인하는 방법 외에 최적화 전략을 사용하는 오일러 함수 방법도 있습니다. 어떤 방법을 사용하든 관계없이 최대한 활용할 수 있는지 여부는 선택한 숫자와 지정하는 간격과 같은 상황적 요인에 따라 크게 좌우되지만, 가능한 두 가지 방법 중에서 정보를 바탕으로 선택하면 전반적인 작업 속도가 실제로 향상될 수 있습니다. 프로그램의 실행 속도. 기술적 능력과 창의적인 문제 해결 능력에 기술적인 지식을 추가하려는 코더의 경우 이러한 방법을 통해 C++로 코소수 계산을 마스터하는 것이 바로 필요할 수 있습니다.
위 내용은 C++에서는 다음을 중국어로 번역합니다. L과 R 사이에서 P에 상대적으로 소수인 숫자의 수를 셉니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
