>

두 정수의 공통 제수를 반환하는이 함수를 작성했습니다. 100000000 범위의 큰 정수로 재귀 적으로 10 회 호출하면 5 초 이상이 걸립니다. 더 빨라지도록 (5 초 미만) 개선하려면 어떻게해야하나요?

commonDivisors :: Int -> Int -> [Int]
commonDivisors x y = if x > y then divisors y x else divisors x y
    where divisors :: Int -> Int -> [Int]
          divisors z n = filter (\x -> n `mod` x == 0 && z `mod` x ==0) [1..n]

  • 답변 # 1

    응용 프로그램을 모르지만 모든 일반 제수 목록을 원한다는 것은 드문 일입니다.

    코드를 최적화하기 위해 Euclid의 알고리즘을 사용하여 두 숫자의 최대 공약수를 찾을 수 있습니다. 이것은 인수보다 적은 모든 숫자를 반복하는 것보다 훨씬 빠릅니다. 더욱이, 두 숫자의 공약수는 가장 큰 공약수의 제수입니다. 따라서 최대 공약수를 찾은 다음 최대 공약수의 모든 약수를 찾는 2 단계 프로세스는 일반적으로 모든 수를 더 작은 요소까지 고려할 필요가 없기 때문에 현재 방법보다 빠릅니다.

    숫자 \ $n \ $의 요소를 찾는 최적화는 \\ n \ $까지만 반복하고 \\ n뿐만 아니라 찾은 모든 요소 \ $k \ $를 목록에 추가하는 것입니다./k \ $. 별도의 아이디어는 \ $n \ $의 소인수 분해를 계산하고 그 요소를 찾는 것입니다.

  • 이전 리눅스 C 포트 노크 구현
  • 다음 algorithm - C의 피보나치 힙