최저 공통 요인

누구나 주어진 두 숫자 중 가장 낮은 공통 인자 (1 제외)를 계산하는 빠른 방법을 제안 할 수 있습니까? 한 가지 방법은 GCD (a, b)> 1, 프라임 인수 분해 (a와 b) 및 결과로 가장 작은 공통 소수 인수 선택 중 하나 일 수 있습니다.최저 공통 요인

더 나은 방법이 있나요?

예 : 결국 LCF (20, 30) = 2, LCF (13,39) = 13

출처

2012-06-25 Vineet Deoraj

이 숙제가 있습니까? 너 뭐 해봤 니? – unwind

이 주제를 다루는 웹에는 수백만 개의 과장된 자원이있을 것입니다. 당신이 시도한 것을 보여주십시오. 그래서 "당신을 위해 일을"여기에 있지 않습니다 ... –

@unwind 아니 숙제가 아니야. 나는 2 차적인 침묵으로 그것을 시도했다. 문제는 더 나은 방법에 관한 것입니다. –

, 난 당신이 소수에 의해 두 숫자를 분할하는 것보다 더 아무것도 찾을 것이라고 생각하지 않습니다 두 개 또는 나눈 값을 구할 때까지의 숫자 sqrt(min(a,b))

출처

2012-06-25 09:10:35 salva

'g = gcd (a, b)'를 먼저 계산하고 가장 작은 소수 요소 'g'를 검색하면 더 좋은 최악의 경우 동작을 얻게됩니다. –

@ 대니얼, 최악의 경우에 맞습니다. 그러나 평균적인 경우 두 개의 난수가 주어지면 통계적으로 보면 lcd가 작은 숫자 일 가능성이 큽니다. 그래서 멍청한 divide-by-primes 방법은 gcd만을 아주 자주 계산하는 것보다 더 빨리 발견 할 것입니다. 어쩌면 2, 3, 5 (사례의 36 %)를 먼저 검사 한 다음 gcd를 계산하고 작은 약수 (7에서 시작)를 찾는 것이 최상의 솔루션이 될 수있는 하이브리드 솔루션 일 수 있습니다. – salva

나는 그것이 정확하다고는 생각하지 않는다. GCD가 1 일 가능성이 높다. GCD를 무시하는 방식을 완전히 망칠 수있다. 나도 그렇게 생각한다. (입력에 특별한 제한이 없다면 (예를 들어, 100 이하의 소수 요소가없는 한) 하이브리드는 먼저 작은 소수를 검사 한 다음 GCD를 수행하면 평균 속도가 가장 빠를 것이라고 생각한다. –

-1

2에서 값 n/2로 루프를 돌립니다. 여기서 n은 두 숫자 중 작은 값입니다. (int i = 2; i < = n/2; i ++)에 대해 으로 루프에 조건을 넣으십시오. (n % i == 0 & &m % i == 0) break 일 경우 ;

i는 필수 항목입니다.

출처

2012-06-25 09:46:09

최저 공통 요인

답변

관련 문제