프로그래밍 (356) 썸네일형 리스트형 [Euler Project 077] 소수의 합으로 표현하는 가짓수 스프레드시트로 표현한 배열이랑, 코드에서 구하는 배열이랑 의미가 조금 다르다. 아래 코드에서는 누적값을 구한다. 그래서 계산의 summation 루프를 줄인다. 위 그림은 이해를 좋게 하기 위해 누적으로 표현하지 않았다. 가로축은 합이 되는 수, 세로축은 소수이다. 2, 2 는 2를 2를 최소한 한번 포함하여 2 이하의 소수들의 합으로 표현하는 갯수로 1이다. 10, 5 는 10을 5를 최소한 한번 포함하여 5 이하의 소수들의 합으로 표현하는 갯수이다. 5+5와 5+3+2가 있는데, 최대 소수인 5를 10에서 뺀 나머지인 5에 대해 경우의 수를 summation 하여 구할 수 있다. 아래는 파이썬 코드. 2차원 배열이 위 스프레드시트의 것과 다른 점 주의하라. #!/usr/bin/env python # .. 2의 거듭제곱 (10만승까지) 벤포드 법칙 무식쟁이 방법으로 확인. #!/usr/bin/env python # http://bomber0.byus.net/index.php/2009/07/30/1409 # brute force check twopow = 1 tenpow = 1 cnt = [ 0 for i in range(10) ] pro = [ 0 for i in range(10) ] for i in range(100000): twopow *= 2 if twopow/(tenpow*10) > 0: tenpow *= 10 #d1 = int(("%d"%twopow)[0]) d = twopow/tenpow #if d1 != d: # print twopow cnt[d] += 1 if (i+1)%1000 == 0: print (i+1) print "%d\t%d\t%d\t%d\t%d\.. [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), .. [Py] 신이 보여준 정리 신이 보여준 정리를 보고 재미있을 것 같아서 짜봤다. 답을 대충 짐작하고 나서는 예쁘게 n + 1 = sqrt(1 + (n) sqrt(1 + (n+1) sqrt(..))) 이 n x (n + 1) = n x sqrt(1 + (n+1) sqrt(...)) 으로 정리되는 걸 알았다. #!/usr/bin/env python # _____________________________ # / ___________________ # / 1 + 2 / ___________ = ? # |/ |/ 1 + 3 |/ ..... # # import math def get_prev(x, n): return math.sqrt(1 + n*x) def eval_first(x0, n): #print "" #print "=========.. 이전 1 ··· 37 38 39 40 41 42 43 ··· 45 다음
