사용자 도구

사이트 도구


ps:소인수분해

소인수분해 (Prime Factorization)

n을 소인수분해하기

  • 다양한 알고리즘이 있는데.. trial division과 Pollard's rho 두가지만 알면 충분하다
    • 페르마의 방법이나 pollard's p-1 은 사실상 몰라도 된다.
  • 소인수분해 결과는 p_1^k_1 * p_2^k_2 * … * p^n^k_n 의 형태로 나온다. 코드를 구현할때는 리턴값으로 p_i를 키로 k_i를 밸류로 갖는 dict를 리턴하도록 만들었다. n이 1일때는 빈 딕셔너리를 리턴.
    • 경우에 따라서는 결과값으로 p배열만 필요한 경우도 있다. 그렇지만 p배열만 리턴하는 함수를 따로 구현하지는 않았다.

Trial division

  • n이 적당히 작은 경우에만 사용 가능하다.
  • 그냥 i=2부터 시작해서 i*i<n이 될때까지 전부 나눠보는 방식. 소수일 경우에 최대 sqrt(n)번의 루프를 돌아야 한다. 시간복잡도는 O(sqrt(n))
  • 소수 체크를 할때와는 다르게 루프를 2~sqrt(n)까지 도는게 아니라, 매번 i*i를 계산해서 n을 넘으면 중단하는 식으로 구현한다. 그 이유는 소인수를 발견하면 n을 그값으로 나누는 작업때문에 n이 점점 작아지기 때문에 이렇게 처리하는것이 보통 더 효율적이기 때문이다. 하지만, n이 소수인 경우에는 사실 이 과정이 불필요하고, 그냥 sqrt(n)을 먼저 구해놓고 거기까지 루프를 도는게 빠르긴 하다. 즉.. 평균적으로는 i*i 로 브레이크하는게 빠르지만, 최악경우에는 sqrt(n) 까지 돌리는게 빠르다는 의미.. 그치만 속도 차이는 별로 없다
  • 역시 wheel optimization 도 가능하다. 2의 배수만 따로 전처리하면 빨라진다. 그 이상은 안해봄
  • 사실상 이 작업에 시간이 걸릴정도로 n이 커질 경우에는 아래에서 설명할 Pollard's Rho를 적용할것이기 때문에, 굳이 상수최적화에 진심을 다할 필요는 없긴 하다..
  • 코드
  • 관련 문제

Pollard's Rho

  • 작성중..
  • 시간복잡도는 O(n^1/4 * logn)

여러개의 수를 소인수분해하기

  • x_1, x_2, …, x_k 를 모두 소인수분해하기. 모든 수는 n이하라고 생각하자.
  • 소인수분해해야 할 수의 갯수 k에 따라서 다음중 적당한 방법들을 선택하면 된다 (n은 trial division으로 소인수분해가 가능한 범위라고 새생각하자)
    • k가 작으면, 그냥 위의 trial division 방법을 모든 x_i에 대해서 적용하면 된다. O(k*n^1/2)
    • k가 적당히 크면, 먼저 sqrt(n)이하의 소수 목록을 모두 계산해놓고, 그것에 대해서만 trial division을 사용할수 있다
      • 에라토스테네스의 체를 이용해서 소수 목록을 구하는 데에 O(sqrt(n)*loglogn)
      • 목록의 소수들만 이용해서 소인수분해를 하는데 O(sqrt(n)/ln(n))
      • k개를 처리하는 총 시간복잡도는 대략 O(sqrt(n)*(loglogn + k/logn)).
      • 관련 문제 - 2312
    • k가 크면 (n에 가까울 정도로), 아래의 방법을 사용하자 O(n + klogn)

[1,n]까지의 모든 수를 소인수분해하기

  • 이경우는, 모든 수에 대해서 최소인수를 계산해 놓는 방식으로 구현한다.
  • 모든수에 대해서 최소인수를 구하는 것은 에라토스테네스의 체 또는 linear sieve를 이용해서 구할수 있다. linear sieve를 이용하는 것이 조금 더 빨랐다. 시간복잡도는 O(n).
  • 모든수의 최소인수를 구하고 나면, 임의의 수 x 의 소인수분해를 O(logx)에 처리할 수 있다.
  • 결과적으로 1~n까지의 모든 수를 소인수분해한다면 O(nlogn) 이 된다
  • 코드
  • 관련 문제

토론

댓글을 입력하세요:
F O Y Y F
 
ps/소인수분해.txt · 마지막으로 수정됨: 2022/07/22 09:03 저자 teferi