본문 바로가기

프로그래밍/알고리즘

[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(int(math.log(LIM, 5))+1):
for b in range(int(math.log((LIM/(5**a)), 3))+1):
count += int(math.log((LIM/((5**a)*(3**b))), 2))+1
'''
for c in range(int(math.log((LIM/((5**a)*(3**b))),2))+1):
print a, b, c, (2**c)*(3**b)*(5**a), LIM
count += 1
'''
print count

LIMIT = 10**9

def GetCount(idx, limit):
# print primes[idx], limit
if primes[idx] == 2:
return int(math.log((limit), 2))+1
else:
count = 0
for pow in range(int(math.log(limit, primes[idx]))+1):
count += GetCount(idx-1, 1.0*limit/(primes[idx]**pow))
return count

primes = [ 2, 3, 5 ]

n = 7
while n <= 100:
for p in primes:
if p*p > n:
primes.append(n)
break
if n%p == 0:
break
n += 1

print primes
count = GetCount(-1, LIMIT)
print count
728x90