주어진 배열의 모든 요소를 ​​나누는 가장 작은 정수 > 1: C++ 사용

이 기사에서는 정수 배열이 제공되며 배열의 모든 요소를 ​​나누는 1보다 큰 가장 작은 숫자를 찾아야 합니다. 예를 들어, 예제 배열 [30, 90, 15, 45, 165]를 고려해 보겠습니다.

으아악

이제 배열의 최대 공약수(GCD)를 찾을 수 있습니다. 결과가 1이면 1만 전체 배열을 나눌 수 있다는 의미이며 -1 또는 "불가능"을 반환할 수 있습니다. 결과가 정수이면 이 정수는 전체 배열을 나눕니다. 그러나 이 정수는 전체 배열을 나누는 가장 작은 정수가 아닐 수도 있습니다. 흥미롭게도 이 정수의 인수는 전체 배열을 나누기도 합니다. 따라서 이 정수(GCD)의 가장 작은 인수를 찾을 수 있다면 전체 배열을 나누는 가장 작은 정수를 갖게 됩니다. 즉, 간단히 말해 배열의 최대 공약수(GCD)를 찾아야 하며 가장 작은 요소가 답입니다.

Example

의 중국어 번역은

Example

입니다.

다음 C++ 코드는 배열의 모든 요소를 ​​나눌 수 있는 1보다 큰 가장 작은 정수를 찾을 수 있습니다. 이는 요소 목록의 최대 공약수를 찾아서 달성할 수 있습니다 -

으아악

출력

으아악

Example

의 중국어 번역은

Example

입니다.

쿼리가 많으면 숫자의 소인수 찾기가 반복됩니다. 체법을 사용하면 숫자의 소인수를 계산할 수 있습니다.

C++에서 1보다 큰 가장 작은 수를 찾는 또 다른 구현 방법은 다음과 같습니다.

으아악

출력

으아악

결론

최소 인수를 얻기 위해 sqrt(n) 방법을 사용했습니다. 이는 최적화될 수 있으므로 시도해 보시기 바랍니다. 시간 복잡도는 O(sqrt(n))입니다. 두 번째 방법의 시간 복잡도는 sieve 방법의 시간 복잡도인 O(nlog(log(n)))입니다. 우리가 설정한 MAX 전역 변수를 기반으로 sieve 방법의 상한을 찾을 수 있습니다.

위 내용은 주어진 배열의 모든 요소를 ​​나누는 가장 작은 정수 > 1: C++ 사용의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!