본문 바로가기

Python

 (69)
[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)!)) 이다. 소스.
[Project Euler 183] 분할곱 http://projecteuler.net/index.php?section=problems&id=183 N이 양의 정수이고, N을 k 개로 똑같이 나누자. r = N/k 즉, N = r + r + ... + r 이다.P를 이 분할의 곱이라고 한다. 즉, P = r x r x ... x r = rk 예를 들어, 11을 다섯 개로 나누면, 11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2 이고, P는P = 2.25 = 51.53632 이다. 그리고, N에 대해 M(N) = Pmax , 즉 P가 갖을 수 있는 최대값으로 정의하자. N = 11일 때에는 다섯 개로 나누었을 때, Pmax = (11/4)4 로 최대가 되고, 다시, M(11) = 14641/256 = 57.19140625, 으로 10진수 ..
[Project Euler 204] 해밍수 해밍수(Hamming number)란 5보다 큰 소수 인수를 갖지 않는 양수를 말한다. 즉, 해밍수를 작은 것부터 몇 개 나열하면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. 108보다 작은 해밍수는 1105개가 있다. 이 개념을 일반화하자. 타잎 n의 일반화된 해밍수를 n보다 큰 소수 인수를 갖지 않는 양수로 정의하자. 즉, 해밍수는 타잎 5의 일반화된 해밍수가 된다. 109보다 작은 타잎 100의 일반화된 해밍수는 몇 개 인가? 재귀로 풀었다. 아래가 코드. #!/usr/bin/env python # Euler Project Problem 204 # Hamming number import math LIM = 10**8 count = 0 for a in range(in..
[Project Euler 148] 파스칼 삼각형 mod 7 http://projecteuler.net/index.php?section=problems&id=148 파스칼 삼각형을 7번째 줄까지 써보면, 7로 나누어 떨어지는 것이 없다는 걸 알 수 있다.: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 그러나, 100번째 줄까지를 보면, 5050개의 숫자 중에서 2361개만 7로 나누어 떨어지지 않는다. 10억(109)번째 줄까지 중에서 7로 나누어 떨어지지 않는 것의 갯수를 구하라. 우선, a+b mod n = (a mod n) + (b mod n) mod n 과 같다는 걸 이용해서 그림을 그려보면, 아주 예쁜 프랙탈모양을 이룸을 알 수 있다. 그리고, 숫자를 7진수로 변환한 후 생각하면 훨씬 생각이..
직육면체가 특정 면으로 착지할 확률 관련 포스팅 http://astralepic.egloos.com/4022771 http://zariski.egloos.com/2229177 http://mcfrog.org/tt/848 #!/usr/bin/env python import math def length(V): sq_sum = 0 for i in xrange(3): sq_sum += V[i]*V[i] return math.sqrt(sq_sum) def dot(U, V): d = 0 for i in xrange(3): d += U[i]*V[i] return d def omega(A, B, C): ''' computes the steradian defined by three vectors A, B, C. ref : http://en.wikipedi..

티스토리툴바