본문 바로가기

오일러프로젝트

 (27)
[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..
[Euler Project 101] 수열 다항식으로 근사하기 #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=101 coff = [ 0 ] * 11 def OP(ord, n): if ord == 0: return coff[0] r = OP(ord-1, n) term = coff[ord] for j in range(1, ord+1): term*=(n-j) for j in range(1, ord+1): term/= j r += term return r def f(n): return 1 - n + n**2 - n**3 + n**4 - n**5 + n**6 - n**7 + n**8 - n**9 + n**10 a = [ f(n) for n in range(1, 12) ] coff[0..
[Euler Project 188] 1777의 1885 거듭거듭제곱의 마지막 8자리 구하기 거듭거듭제곱이란 단어는 tetration의 정확한 한국어 번역어를 몰라서 내가 개발한 번역임. 정확한 정의는 검색하여 보기바람. 매우 재미있음. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=188 def phi(n0): ''' euler phi function for n, which consists of only 2 and 5 ''' n = n0 pow2 = 0 while n%2 == 0: n/=2 pow2 +=1 n = n0 pow5 = 0 while n%5 == 0: n/=5 pow5 +=1 if pow5 == 0: if pow2 == 0: return 1 else: return 2**(pow2-1) els..
[Euler Project 187] 인자가 두개인 합성수의 갯수 1억보다 작은, 소수 둘만의 곱인 합성수의 갯수를 구하라. 4나 9도 포함된다. 에라스토테네스의 체 방법으로 소수를 우선 싹 구하고 한다. 내가 가장 효율적이라고 생각했던 소수 구하는 방법은 전혀 효율적이지 않았다. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=187 MAX=50000000 flags = [ 1 ] * MAX flags[0] = 0 flags[1] = 0 for n in range(2, MAX): if flags[n] == 1: m = 2*n while m < MAX: flags[m] = 0 m+=n n+=1 primes = [ ] for i in range(0, MAX): if flags[i]..
[Euler Project 091] 직각삼각형 갯수 구하기 50, 50 격자 안에서 한 꼭지점이 원점에 있고, 꼭지점이 격자점에 위치하는 직각삼각형의 갯수 구하기. 오일러 프로젝트 91번 문제이다. 직각이 원점에 있는 경우, 직각이 축에 위치하는 경우, 그리고 나머지 경우에 대해 나누어 갯수를 구했다. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=91 def get_cnt_when_right_angle_is_O(max): ''' P is (0, [1 ... max]) and Q is ([1 ... max], 0)''' return max * max def get_cnt_when_right_angle_is_on_axis(max): ''' When P is (0, y), ..
[수학] 페르마 소정리 이해를 위한 장난 rsa를 주제로 한 오일러 프로젝트 문제를 풀다가, 페르마 소정리에 대해서 감이 잘 안 와서 엑셀로 계산을 시켜봤다. p = 3, q = 7 인 상당히 간단한 경우의 계산이다. 엑셀이 상당한 프로그래밍 시간을 줄여주기는 하는데, 내 입맛에 딱 맞춰 결과를 보기에는 아직 익숙하지가 않아서 좀 고달픈 구석이 있다.
[Project Euler 213] 30x30 격자 벼룩 http://projecteuler.net/index.php?section=problems&id=213 30x30 크기의 격자에 벼룩이 있다. 최초에 벼룩은 격자 하나당 하나씩 있고, 한 번 종이 울리면, 격자의 사방으로 튈 수 있다. 가장자리에 있는 벼룩은 바깥으로 나갈 수 없다. 종이 울릴 때마다 각 격자에 벼룩이 몇마리 있을지에 대한 확률분포를 색으로 표현하는 걸 만들어 봤다. 문제가 풀릴려면 부동소수점연산에 의한 오차가 문제가 될 것 같으나, 대략적인 것만 보기 위해서, 그런 건 우선 무시하고 만들어 봤다. 10번 종이 울린 후 확률 분포는 다음과 같다. 색이 흐리면 (하얀색에 가까우면) 확률이 낮은 것이다. vc6.0, mfc 로 짜봤으며, 소스는 여기 있다. 대충 짠거라 책임은 지지 않는다. ..
[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진수 ..

티스토리툴바