Problem:


ハミング数

1 に 2, 3, 5 を何回か (0 回以上) かけ算して得られる数をハミング数 (Hamming numbers) と呼びます。例えば、

1

1 × 2 × 2 = 4

1 × 2 × 2 × 3 × 5 × 5 = 300

などはハミング数ですが、11, 13, 14 などはハミング数ではありません。

ハミング数はどれも 60 のべき乗を割り切る(例えば、54 は 603 = 21600 を割り切る) ので、時刻など 60 進法の計算には都合の良い数として昔から知られていました。また、楽器の調律に用いる音階の一つである純正律では、音の周波数の比が 24, 27, 30, 32, 36, 40, 45, 48 というハミング数からなる数列になります。

整数 m、n を入力とし、m 以上 n 以下のハミング数の個数を出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。

各データセットとして、２つの整数 m と n (1 ≤ m, n ≤ 1000000, m ≤ n) が空白区切りで１行に与えられます。

データセットの数は 20 を超えません。

Output

データセットごとに m 以上 n 以下のハミング数の個数を１行に出力します。

Sample Input

3 8
1 27
1 86
0

Output for the Sample Input

5
17
31



Sample input:
3 8
1 27
1 86
0


Sample output:
5
17
31

Submission status: Wrong Answer

Solution code:
while 1:
  try: m, n = map(int, raw_input().split())
  except: break
  x = [1]
  for b in [2, 3, 5]:
    A = []
    for a in x:
      while a<=n:
        A.append(a)
        a *= b
    x = list(set(x+A))
  i=0
  while x[i]<m: i+=1
  print len(x)-i

Submission status: Wrong Answer

Solution code:
def hum(n):
  x = [0]*n
  x[1] = 1
  for e in [2, 3, 5]:
    for i in range(n/e):
      if x[i]: x[i*e] = 1
  return x

M = []
N = []
while 1:
  try: m,n = map(int, raw_input().split())
  except: break
  M.append(m)
  N.append(n)
H = hum(max(N)+1)
for m, n in zip(M,N):
  print sum(H[m:n+1])

Submission status: Wrong Answer

Solution code:
import sys
def main():
    for line in sys.stdin:
        mn = list(line)
        if mn[0] == "0":
            break
        else:
            num = [str(i) for i in range(0, 10)]
            d = ""
            for x in range(len(mn)):
                if mn[x] not in num:
                    dd = x
                    break
                else:
                    d += mn[x]
            m = int(d)

            d = ""
            for y in range(dd + 1, len(mn) - 1):
                d += mn[y]
            n = int(d)

            a2 = []
            for i in range(1, n):
                hoge = 2 ** i
                if hoge <= n:
                    a2.append(hoge)
                else:
                    break

            a3 = []
            for i in range(1, n):
                hoge = 3 ** i
                if hoge <= n:
                    a3.append(hoge)
                else:
                    break

            a5 = []
            for i in range(1, n):
                hoge = 5 ** i
                if hoge <= n:
                    a5.append(hoge)
                else:
                    break
            a23 = []
            for i in range(len(a2)):
                for j in range(len(a3)):
                    fuga = a2[i] * a3[j]
                    if fuga <= n:
                        a23.append(fuga)
                    else:
                        break

            a35 = []
            for i in range(len(a3)):
                for j in range(len(a5)):
                    fuga = a3[i] * a5[j]
                    if fuga <= n:
                        a35.append(fuga)
                    else:
                        break

            a52 = []
            for i in range(len(a5)):
                for j in range(len(a2)):
                    fuga = a5[i] * a2[j]
                    if fuga <= n:
                        a52.append(fuga)
                    else:
                        break

            a2335 = []
            for i in range(len(a23)):
                for j in range(len(a35)):
                    fuga = a23[i] * a35[j]
                    if fuga <= n:
                        a2335.append(fuga)
                    else:
                        break

            a3552 = []
            for i in range(len(a35)):
                for j in range(len(a52)):
                    fuga = a35[i] * a52[j]
                    if fuga <= n:
                        a3552.append(fuga)
                    else:
                        break

            a23353552 = []
            for i in range(len(a2335)):
                for j in range(len(a3552)):
                    fuga = a2335[i] * a3552[j]
                    if fuga <= n:
                        a23353552.append(fuga)
                    else:
                        break

            a30 = []
            i = 1
            while 1:
                fuga = 30 * i
                if fuga <= n:
                    a30.append(fuga)
                    i += 1
                else:
                    break

            a = a2 + a3 + a5 + a23 + a35 + a52 + a2335 + a3552 +\
                a23353552 + a30

            if m == 1:
                a.append(1)
            else:
                pass
            a = sorted(set(a))

            for x in range(len(a)):
                if a[x] >= m:
                    c = x
                    break
                else:
                    pass

            cnt = 0
            for x in range(c, len(a)):
                 cnt += 1

            print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
while True:
    try:
        m, n = map(int, raw_input().split())

        c = 0
        for i in range(m, n + 1):
            if i % 2 == 0 or i % 3 == 0 or i % 5 == 0:
                c += 1

        print c
        
    except ValueError:
        break

Submission status: Wrong Answer

Solution code:
from bisect import bisect
MAXN = 1000002
ham = [False]*MAXN
def func(n):
    if not (n>MAXN or ham[n]):
        ham[n] = True
        for m in [2,3,5]:
            func(m*n)
func(1)
H = filter(lambda i:ham[i],xrange(MAXN))
while True:
    line = raw_input()
    if line == "0":
        break
    m,n = map(int,line.split())
    print bisect(H,n)-bisect(H,m)+1

Submission status: Accepted

Solution code:
def hum(n):
  x = [0]*(n+1)
  x[1] = 1
  for e in [2, 3, 5]:
    for i in range(n/e+1):
      if x[i]: x[i*e] = 1
  return x

M = []
N = []
while 1:
  try: m,n = map(int, raw_input().split())
  except: break
  M.append(m)
  N.append(n)
H = hum(max(N))
for m, n in zip(M,N):
  print sum(H[m:n+1])

Submission status: Accepted

Solution code:
def f(x, I, n):
  while x[-1]<=n:
    a = [x[I[0]]*2, x[I[1]]*3, x[I[2]]*5]
    b = min(a)
    c = a.index(b)
    if b > x[-1]: x += [b]
    I[c] += 1
  return

while 1:
  try: m,n = map(int, raw_input().split())
  except: break
  x = [1]
  I = [0, 0, 0]
  f(x, I, m-1)
  a = len(x)
  f(x, I, n)
  print len(x)-a

Submission status: Accepted

Solution code:
def two(n):
    if n == 1:
        return True
    elif n%2 != 0:
        return three(n)
    else:
        q = n/2
        return two(q)

def three(n):
    if n == 1:
        return True
    elif n%3 != 0:
        return five(n)
    else:
        q = n/3
        return three(q)

def five(n):
    if n == 1:
        return True
    elif n%5 != 0:
        return False
    else:
        q = n/5
        return two(q)

while True:
    input_line = raw_input()
    if input_line == '0': break
    m, n = map(int, input_line.split())
    c = 0
    for n in range(m, n+1):
        if two(n):
            c += 1
    else:
        print c

Submission status: Accepted

Solution code:
def two(n):
    if n == 1:
        return True
    elif n%2 != 0:
        return three(n)
    else:
        q = n/2
        return two(q)

def three(n):
    if n == 1:
        return True
    elif n%3 != 0:
        return five(n)
    else:
        q = n/3
        return three(q)

def five(n):
    if n == 1:
        return True
    elif n%5 != 0:
        return False
    else:
        q = n/5
        return five(q)

while True:
    input_line = raw_input()
    if input_line == '0': break
    m, n = map(int, input_line.split())
    c = 0
    for n in range(m, n+1):
        if two(n):
            c += 1
    else:
        print c

Submission status: Accepted

Solution code:
while 1:
    n=list(map(int,input().split()))
    if n[0]==0:break
    a=0
    for i in range(n[0],n[1]+1):
        b=i
        while b%2==0: b/=2
        while b%3==0: b/=3
        while b%5==0: b/=5
        if b==1:a+=1
    print(a)

Submission status: Accepted

Solution code:
while 1:
    n=list(map(int,input().split()))
    if n[0]==0:break
    a=0
    for i in range(n[0],n[1]+1):
        b=i
        while b%5==0: b/=5
        while b%3==0: b/=3
        while b%2==0: b/=2
        if b==1:a+=1
    print(a)

Submission status: Accepted

Solution code:
isHamming = []

def judge():
	global isHamming;
	isHamming[1] = True
	i = 1
	while True:
		if (i * 2 > 1000000):
			break
		if (isHamming[i]):
			isHamming[i * 2] = True
		i += 1
	
	i = 1
	while True:
		if (i * 3 > 1000000):
			break
		if (isHamming[i]):
			isHamming[i * 3] = True
		i += 1
	
	i = 1
	while True:
		if (i * 5 > 1000000):
			break
		if (isHamming[i]):
			isHamming[i * 5] = True
		i += 1

def init():
	global isHamming
	for i in range(1000000 + 1):
		isHamming.append(False)

init()
judge()
while True:
	m = [int(num) for num in input().split()]
	if m == [0]:
		break;
		
	count = 0
	for i in range(m[0], m[1] + 1):
		if (isHamming[i]):
			count += 1;
			
	print(count)

Submission status: Accepted

Solution code:
# Aizu Problem 00161: Sport Meet
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


N = 1000000
hamming = [False] * (N + 1)
ans = [0] * (N + 1)
hamming[1] = True
ans[1] = 1
for k in range(2, N + 1):
    if (k % 2 == 0 and hamming[k//2]) or \
       (k % 3 == 0 and hamming[k//3]) or (k % 5 == 0 and hamming[k//5]):
        hamming[k] = True
    ans[k] = ans[k-1]
    if hamming[k]:
        ans[k] += 1


while True:
    s = [int(_) for _ in input().split()]
    if len(s) == 1 and s[0] == 0:
        break
    m, n = s[:]
    print(ans[n] - ans[m-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0162

"""
import sys
from sys import stdin
from bisect import bisect_right, bisect_left
input = stdin.readline


def main(args):
    hammings = []

    temp = set()
    for i in range(21):
        for j in range(14):
            for k in range(9):
                ans = 2**i * 3**j * 5**k
                temp.add(ans)

    hammings = list(temp)
    hammings.sort()

    while True:
        try:
            m, n = map(int, input().split(' '))
        except ValueError:
            break

        s = bisect_left(hammings, m)
        t = bisect_right(hammings, n)

        print(t - s)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0162

"""
import sys
from sys import stdin
from bisect import bisect_right, bisect_left
from math import ceil, log
input = stdin.readline


def main(args):
    hammings = []

    temp = set()
    for i in range(ceil(log(1e6, 2)) + 1):
        for j in range(ceil(log(1e6, 3)) + 1):
            for k in range(ceil(log(1e6, 5)) + 1):
                ans = 2**i * 3**j * 5**k
                temp.add(ans)

    hammings = list(temp)
    hammings.sort()

    while True:
        try:
            m, n = map(int, input().split(' '))
        except ValueError:
            break

        s = bisect_left(hammings, m)
        t = bisect_right(hammings, n)

        print(t - s)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def hammingp(n):
    while n % 2==0:
        n /= 2
    while n % 3==0:
        n /= 3
    while n % 5==0:
        n /= 5
    return(n==1)

while True:
    s = list(map(int,input().strip().split()))
    if len(s)==1:
        break
    m,n = s

    c=0
    for i in range(m,n+1):
        if hammingp(i):
            c += 1
    print(c)

Submission status: Accepted

Solution code:
MAX = 1000000

hamming_list = [False] * (MAX + 1)

hamming_list[0] = False
hamming_list[1] = True

for index in range(2, MAX + 1):

    if index / 2 % 1 == 0:
        if hamming_list[index // 2]:
            hamming_list[index] = True
    elif index / 3 % 1 == 0:
        if hamming_list[index // 3]:
            hamming_list[index] = True
    elif index / 5 % 1 == 0:
        if hamming_list[index // 5]:
            hamming_list[index] = True

while True:

    input_data = input()

    if input_data == "0":
        break

    start, end = [int(item) for item in input_data.split(" ")]

    count = sum(hamming_list[start:end + 1])
    print(count)

Submission status: Accepted

Solution code:
MAX = 1000000

hamming_list = [False] * (MAX + 1)

hamming_list[0] = False
hamming_list[1] = True

for index in range(2, MAX + 1):

    if index % 2 == 0:
        if hamming_list[index // 2]:
            hamming_list[index] = True
    elif index % 3 == 0:
        if hamming_list[index // 3]:
            hamming_list[index] = True
    elif index % 5 == 0:
        if hamming_list[index // 5]:
            hamming_list[index] = True

while True:

    input_data = input()

    if input_data == "0":
        break

    start, end = [int(item) for item in input_data.split(" ")]

    count = sum(hamming_list[start:end + 1])
    print(count)

Submission status: Accepted

Solution code:
twos =   [2 ** i for i in range(21) if 2 ** i <= 1000000]
threes = [3 ** i for i in range(21) if 2 ** i <= 1000000]
fives =  [5 ** i for i in range(21) if 2 ** i <= 1000000]
muls = [x * y * z for x in twos for y in threes for z in fives]
muls.sort()
def under(n):
  cnt = 0
  for i in muls:
    if i <= n:
      cnt += 1
    else:
      break
  return cnt

while True:
  s = input()
  if s == "0":
    break

  m, n = map(int, s.split())
  print(under(n) - under(m - 1))

Submission status: Accepted

Solution code:
# AOJ 0162 Hamming Numbers
# Python3 2018.6.23 bal4u

MAX = 1000000

t = [0]*(MAX+5)

a5 = 1
for i in range(9):
	a3 = 1
	for j in range(13):
		a35 = a5*a3
		if a35 > MAX: break
		a2 = 1
		for k in range(20):
			if a35*a2 > MAX: break
			t[a35*a2] = 1
			a2 <<= 1
		a3 *= 3
	a5 *= 5
while 1:
	a = input()
	if a == '0': break
	m, n = map(int, a.split())
	print(sum(t[m:n+1]))

Submission status: Accepted

Solution code:
while True:
    d=raw_input()
    if d=="0":break
    m,n=map(int,d.split())
    cnt=0
    for i in range(m,n+1):
        t=i
        while t!=1:
            if t%2==0:
                t/=2
            elif t%3==0:
                t/=3
            elif t%5==0:
                t/=5
            else:
                break
        else:
            cnt+=1
    print cnt

Submission status: Accepted

Solution code:
import math

while True:
    try:
        m, n = map(int, raw_input().split())

        f2 = int(math.log(n, 2)) + 1
        f3 = int(math.log(n, 3)) + 1
        f5 = int(math.log(n, 5)) + 1

        c = 0
        for i in range(f2):
            for j in range(f3):
                for k in range(f5):
                    if m <= (2 ** i) * (3 ** j) * (5 ** k) <= n:
                        c += 1
        print c

    except ValueError:
        break

Submission status: Accepted

Solution code:
import math

while True:
    try:
        m, n = map(int, raw_input().split())

        f2 = int(math.log(n, 2))
        f3 = int(math.log(n, 3))
        f5 = int(math.log(n, 5))

        count = 0
        for i in range(f2 + 1):
            for j in range(f3 + 1):
                for k in range(f5 + 1):
                    if m <= (2 ** i) * (3 ** j) * (5 ** k) <= n:
                        count += 1
        print count

    except ValueError:
        break

Submission status: Accepted

Solution code:
from bisect import bisect,bisect_left
MAXN = 1000002
ham = [False]*MAXN
def func(n):
    if not (n>MAXN or ham[n]):
        ham[n] = True
        for m in [2,3,5]:
            func(m*n)
func(1)
H = filter(lambda i:ham[i],xrange(MAXN))
while True:
    line = raw_input()
    if line == "0":
        break
    m,n = map(int,line.split())
    print bisect(H,n)-bisect_left(H,m)

Submission status: Accepted

Solution code:
from bisect import bisect,bisect_left
from fractions import gcd
MAXN = 1000002
T = 2**20*3**14*5**9
H = filter(lambda i:gcd(T,i)==i,xrange(MAXN))
while True:
    line = raw_input()
    if line == "0":
        break
    m,n = map(int,line.split())
    print bisect(H,n)-bisect_left(H,m)

Submission status: Accepted

Solution code:
while 1:
    ipt = raw_input()
    if ipt=="0": break
    m,n = map(int, ipt.split())
    ans = 0
    for i in xrange(m,n+1):
        p = i
        while p>1:
            if p%2==0:
                p/=2
            elif p%3==0:
                p/=3
            elif p%5==0:
                p/=5
            else: break
        if p==1: ans+=1
    print ans

Submission status: Accepted

Solution code:
while True:
	inp = raw_input()
	if inp == "0": break
	m,n = map(int, inp.split())
	ans = 0
	for i in range(m,n+1):
		while i > 1:
			if i%2 == 0:
				i /= 2
			elif i%3 == 0:
				i /= 3
			elif i%5 == 0:
				i /= 5
			else:
				break
		else:
			ans += 1
	print ans

Submission status: Accepted

Solution code:
def ham2(a):
	global m,n,count
	if m <= a:
		count += 1
	a2,a3,a5 = a*2, a*3, a*5
	if a2 <= n: ham2(a2)
	if a3 <= n:	ham3(a3)
	if a5 <= n:	ham5(a5)

def ham3(a):
	global m,n,count
	if m <= a:
		count += 1
	a3,a5 = a*3, a*5
	if a3 <= n:	ham3(a3)
	if a5 <= n:	ham5(a5)
	
def ham5(a):
	global m,n,count
	if m <= a:
		count += 1
	a5 = a*5
	if a5 <= n:	ham5(a5)

while True:
	inp = raw_input()
	if inp == "0": break
	m,n = map(int, inp.split())
	count = 0
	ham2(1)
	print count

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


SIZE_2 = 20
SIZE_3 = 13
SIZE_5 = 9
NUM = 1000001

POW_2 = [1]*SIZE_2
for i in range(1,SIZE_2):
    POW_2[i] = POW_2[i-1]*2

POW_3 = [1]*SIZE_3
for i in range(1,SIZE_3):
    POW_3[i] = POW_3[i-1]*3

POW_5 = [1]*SIZE_5
for i in range(1,SIZE_5):
    POW_5[i] = POW_5[i-1]*5

table = [0]*(NUM)

for i in range(SIZE_2):
    for k in range(SIZE_3):
        if POW_2[i]*POW_3[k] >= NUM:
            break
        for p in range(SIZE_5):
            if POW_2[i]*POW_3[k]*POW_5[p] >= NUM:
                break
            table[POW_2[i]*POW_3[k]*POW_5[p]] = 1

for i in range(1,NUM):
    table[i] += table[i-1]

while True:
    tmp_str = input()
    if len(tmp_str) == 1 and tmp_str[0] == "0":
        break
    left,right = map(int,tmp_str.split())
    print("%d"%(table[right]-table[left-1]))

Submission status: Accepted

Solution code:
while True:
    A = list(map(int, input().split()))
    if A[0] == 0:
        break
 
    n, m = A[0], A[1]
    ans = 0
    for i in range(n, m+1):
        b = i
        while b % 5 == 0:
            b //= 5
        while b % 3 == 0:
            b //= 3
        while b % 2 == 0:
            b //= 2
        if b == 1:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    datas = list(map(int, input().split()))
    if datas[0] == 0:
        break

    n, m = datas[0], datas[1]
    cnt = 0
    for i in range(n, m+1):
        b = i
        while b % 5 == 0:
            b //= 5
        while b % 3 == 0:
            b //= 3
        while b % 2 == 0:
            b //= 2
        if b == 1:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n == '0': break
    m, n = map(int, n.split())
    cnt = 0
    for i in range(m, n+1):
        num = i
        while num % 5 == 0:
            num /= 5
        while num % 3 == 0:
            num /= 3
        while num % 2 == 0:
            num /= 2
        if num == 1:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
H = [False for i in range(1000001)]

H[1] = True
for i in range(20):
    for j in range(13):
        for k in range(9):
            if (2 ** i) * (3 ** j) * (5 ** k) < 1000001:
                H[(2 ** i) * (3 ** j) * (5 ** k)] = True
            else:
                break

while True:
    L = input()
    if L == "0":
        break

    a, b = [int(i) for i in L.split()]
    ans = 0
    for i in range(a, b+1):
        if H[i]:
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
num = [2,3,5]
M = 10**6; S = [0]*(M+2); S[1] = 1; s = 0;
for i in xrange(1,M+1):
    if S[i]==1:
        for j in xrange(3):
            S[min(M+1,num[j]*i)] = 1;
        s += 1
    S[i] = s
while 1:
    try:
        m,n = map(int, raw_input().split())
        print S[n]-S[m-1]
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
num = [2,3,5]
M = 10**6; S = [0]*(M+2); S[1] = 1; s = 0;
i = 0;
while(i<M+1):
    if S[i]==1:
        for j in xrange(3):
            S[min(M+1,num[j]*i)] = 1;
        s += 1
    S[i] = s
    i+=1
while 1:
    try:
        m,n = map(int, raw_input().split())
        print S[n]-S[m-1]
    except EOFError:
        break

Submission status: Runtime Error

Solution code:
while 1:
    try:
        n,m = map(int, raw_input().split())
        ans = 0
        for i in xrange(n,m+1):
            p = i
            while p>1:
                if p%2==0:
                    p/=2
                elif p%3==0:
                    p/=3
                elif p%5==0:
                    p/=5
                else: break
            if p==1: ans+=1
        print ans
    except EOFError:
        break