結果

問題 No.371 ぼく悪いプライムじゃないよ
ユーザー lam6er
提出日時 2025-03-20 20:53:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,900 bytes
コンパイル時間 436 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 103,876 KB
最終ジャッジ日時 2025-03-20 20:54:36
合計ジャッジ時間 21,114 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def sieve(n):
    if n < 2:
        return []
    sieve_list = [True] * (n + 1)
    sieve_list[0] = sieve_list[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if sieve_list[i]:
            sieve_list[i*i : n+1 : i] = [False] * len(sieve_list[i*i : n+1 : i])
    primes = [i for i, val in enumerate(sieve_list) if val]
    return primes

def is_prime(n):
    if n < 2:
        return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n % p == 0:
            return n == p
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def find_largest_prime(start, primes_list):
    n = start
    while n >= 2:
        if is_prime(n):
            return n
        n -= 1
    return None

def main():
    L, H = map(int, input().split())
    sqrt_H = math.isqrt(H)
    primes = sieve(sqrt_H)
    primes_desc = sorted(primes, reverse=True)
    max_p = -1
    result_x = -1

    for p in primes_desc:
        q_list = []
        for q in primes:
            if q >= p:
                break
            q_list.append(q)
        q_list_sorted = q_list  # Already sorted ascending in sieve

        k_max = H // p
        k_min = (L + p - 1) // p  # ceil division
        k_min = max(k_min, 2)
        if k_min > k_max:
            continue
        found = False
        for k in range(k_max, k_min - 1, -1):
            divisible = False
            for q in q_list_sorted:
                if k % q == 0:
                    divisible = True
                    break
            if not divisible:
                x = p * k
                if L <= x <= H:
                    if p > max_p or (p == max_p and x > result_x):
                        max_p = p
                        result_x = x
                    found = True
                    break
        if found:
            continue  # Check next p

        # Check p*q form where q is a prime >=p
        q_max = H // p
        q_min = p
        if q_max < q_min:
            continue
        q_candidate = find_largest_prime(q_max, primes)
        if q_candidate is not None and q_candidate >= q_min:
            x = p * q_candidate
            if L <= x <= H:
                if p > max_p or (p == max_p and x > result_x):
                    max_p = p
                    result_x = x

        x_p_sq = p * p
        if L <= x_p_sq <= H:
            if p > max_p or (p == max_p and x_p_sq > result_x):
                max_p = p
                result_x = x_p_sq

    # Check if sieve's primes didn't cover all possibilities (e.g., p=2 with q above sieve range)
    if result_x == -1:
        primes.append(2)
        for p in [2]:
            q_list = []
            for q in primes:
                if q >= p:
                    break
                q_list.append(q)
            q_list_sorted = q_list

            k_max = H // p
            k_min = (L + p - 1) // p
            k_min = max(k_min, 2)
            if k_min > k_max:
                continue
            for k in range(k_max, k_min - 1, -1):
                divisible = False
                for q in q_list_sorted:
                    if k % q == 0:
                        divisible = True
                        break
                if not divisible:
                    x = p * k
                    if L <= x <= H:
                        if p > max_p or (p == max_p and x > result_x):
                            max_p = p
                            result_x = x
                        break

    print(result_x)

if __name__ == "__main__":
    main()
0