[zerojudge] d366: 00294 - Divisors

from sys import stdin
import math

# 先用篩法建一小段質數
u = 100
sieve = [0, 0, 2, 3] + [1] * (u - 4)
prime = [2]
for i in range(3, u, 2):
    if(sieve[i] == 0): continue
    prime.append(i)
    for j in range(i * i, u, i): 
        sieve[j] = 0
#######################    
def isPrime(n):
    '''
    參考 http://www.csie.ntnu.edu.tw/~u91029/Prime.html
    質數判定
    ''' 
    if(n == 2): return 1
    if(n%2 == 0): return 0
    if(n%6 not in [1,5]): return 0
    u = n - 1
    t = 0
    while(u % 2 == 0):
        u >>= 1
        t += 1
    sprp = [2, 7, 61]
    for sk in sprp:
        a = sk % n
        if (a == 0 or a == 1 or a == n-1): continue
        x = pow(a, u, n)
        if (x == 1 or x == n-1): continue
        for i in range(t-1):
            x = pow(x, 2, n)
            if (x == 1): return 0
            if (x == n-1): break
        if (x != n-1): return 0
    return 1

def factorize(n):
    # 因數分解   
    # 參考網路上的解法，非原創
    if(isPrime(n)): return 1, n, 1
    x_fixed = 2
    cycle_size = 2
    x = 2
    factor = 1

    while factor == 1:
        count = 1
        while count <= cycle_size and factor <= 1:
            x = (x*x + 1) % n
            factor = math.gcd(x - x_fixed, n)
            count += 1
        cycle_size *= 2
        x_fixed = x
    c = 0
    while(n % factor == 0):
        n //= factor
        c += 1
    return n, factor, c
    
def 計算因數(n):
    if(n == 1): return 1
    if(isPrime(n)): return 2
    k = int(n ** 0.5) # 上限
    r = 1
    for x in prime:
        if(x > k): break
        c = 0
        while(n % x == 0):
            c += 1
            n //= x
        r *= (c + 1)
    '''
    先用建立好的一小段質數表試除
    剩餘的用 factorize 分解
    '''    
    while(n > 1):
        n, y, z = factorize(n)
        r *= (z + 1)
        if(n == 1): break
    return r

N = int(stdin.readline()) # 測資筆數
for i in range(N):
    L, U = map(int, stdin.readline().split())
    P, D = 0, 0
    for j in range(L, U+1):
        tmp = 計算因數(j)
        if(tmp > D):
            P, D = j, tmp
    print('Between {} and {}, {} has a maximum of {} divisors.'.format(L, U, P, D))