본문 바로가기

소인수분해

(4)
[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 0 { factors.append((p, pow)) } p += 1 pow = 0 } if n != 1 { factors.append((n, 1)) } return factors } func primeFactors(_ n: Int) -> [(Int, Int)]..
[EP 047] 소인수분해의 소수의 갯수가 4개 문제는 이렇다. 644는 소인수분해하였을 때, 22 x 7 x 23 으로 세 개의 서로다른 소수로 이루어진다. n, n+1, n+2, n+3 이 모두 네 개의 서로다른 소수로 이루어지는 최소의 n을 구하라. 1부터 차례대로 소인수분해를 해 나가야 하기 때문에, 완전한 소수의 리스트를 관리할 수 있다. 소수판정이 매우 효율적이라서 기쁘다. 또한 소인수분해를 기록하는 리스트도 기록해 나가는데, 일단 하나의 소수만 발견하면 기록된 리스트를 이용해서 매우 효율적으로 원하는 값을 구할 수 있다. 소스를 봐라. # Author : DwYoon # PROJECT EULER # http://projecteuler.net/index.php?section=problems&id=47 # PROBLEM 47 import ti..
[Euler Project 203] 소수제곱없는 이항계수의 합 구하기 0C0 부터 50C50 까지의 이항계수들 가운데에 소인수분해하여, 제곱이상의 인자가 없는 것들의 합을 구하는 것. 트릭은 nCr = n x ((n-1)C(r-1) / r 이라는 관계식을 이용하는 것, 수를 50이하의 소수 (15개)의 거듭제곱수의 리스트로 표현하여 곱과 나누기의 오버헤드를 줄이고, 제곱 이상의 인자가 없는지 확인하기 편하게 하는 것.아래 코드는 좀 지져분하다. #!/usr/bin/env python def MUL(l1, l2, l3): n = len(primes) #l3 = [ 0 ] * n for i in range(n): l3[i] = l1[i]+l2[i] return def DIV(l1, l2, l3): n = len(primes) #l3 = [ 0 ] * n for i in ran..
[Projet Euler 231] 조합의 소인수분해 문제 이항계수 10C3 = 120 이다. 120 = 23 × 3 × 5 = 2 × 2 × 2 × 3 × 5 이고, 2 + 2 + 2 + 3 + 5 = 14 이 된다. 즉 10C3 의 소인수분해하여 나온 인자의 합은 14이다. 20000000C15000000 의 소인수분해 인자의 합을 구하라. http://projecteuler.net/index.php?section=problems&id=231 풀이법. 130! 마지막엔 0이 몇 개 있는지를 풀어내는 방법을 응용한다. 사실 동일한 거다. 일반적으로 m! 에 소수 p가 몇 개 있는지 구하는 식은 [m/p] + [m/(p*p)] + [m/(p*p*p)] + [m/(p*p*p*p)] + ... 이다. nCm = n!/((m!)((n-m)!)) 이다. 소스.