[Swift] 소인수분해

swift 로 소인수분해하는 코드를 짜 봤다. 정수를 인자로 주면, 그 정수의 소인수분해를 (소수, 거듭제곱수) 의 어레이로 반환한다. 1은 빈 어레이를 반환한다.

#!/usr/bin/env swift

import Foundation

func primeFactors0(_ n: Int) -> [(Int, Int)] {
  var factors: [(Int, Int)] = []
  var p = 2
  var pow = 0
  var n = n

  while p * p <= n {
    while n % p == 0 {
      pow += 1
      n /= p
    }
    if pow > 0 { factors.append((p, pow)) }
    p += 1
    pow = 0
  }

  if n != 1 {
    factors.append((n, 1))
  }

  return factors

}

func primeFactors(_ n: Int) -> [(Int, Int)] {
  var factors: [(Int, Int)] = []
  var p = 2
  var pow = 0
  var n = n

  while n % p == 0 {
    pow += 1
    n /= p
  }
  if pow > 0 { factors.append((p, pow)) }
  p += 1
  pow = 0

  while p * p <= n {
    while n % p == 0 {
      pow += 1
      n /= p
    }
    if pow > 0 { factors.append((p, pow)) }
    p += 2
    pow = 0
  }

  if n != 1 {
    factors.append((n, 1))
  }

  return factors

}



func main() {

  for n in [1, 2, 3, 4, 22, 36, 60, 61, 9002, 90001, 90002, 90003, 3*4*5*6*7*8*9*10, 90000003] {
    print(n, primeFactors(n))
  }

}

main()

1 []
2 [(2, 1)]
3 [(3, 1)]
4 [(2, 2)]
22 [(2, 1), (11, 1)]
36 [(2, 2), (3, 2)]
60 [(2, 2), (3, 1), (5, 1)]
61 [(61, 1)]
9002 [(2, 1), (7, 1), (643, 1)]
90001 [(90001, 1)]
90002 [(2, 1), (11, 1), (4091, 1)]
90003 [(3, 1), (19, 1), (1579, 1)]
1814400 [(2, 7), (3, 4), (5, 2), (7, 1)]
90000003 [(3, 1), (30000001, 1)]