結果

問題 No.371 ぼく悪いプライムじゃないよ
ユーザー lam6er
提出日時 2025-03-26 15:51:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,183 bytes
コンパイル時間 320 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 76,476 KB
最終ジャッジ日時 2025-03-26 15:52:35
合計ジャッジ時間 5,289 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

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

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

L, H = map(int, input().split())
sqrt_H = math.isqrt(H)
primes = sieve(sqrt_H)
primes.sort(reverse=True)

p_max = -1
x_max = -1

for p in primes:
    # Case a: p squared
    x_a = p * p
    valid_a = L <= x_a <= H
    
    # Case b: p * k where k is >= p and not divisible by any prime < p
    k_max = H // p
    valid_b = False
    x_b = -1
    if k_max >= p:
        primes_less_than_p = [q for q in primes if q < p]
        found_k = None
        for k in range(k_max, p - 1, -1):
            divisible = False
            for q in primes_less_than_p:
                if k % q == 0:
                    divisible = True
                    break
            if not divisible:
                found_k = k
                break
        if found_k is not None:
            x_b_candidate = p * found_k
            if x_b_candidate >= L:
                x_b = x_b_candidate
                valid_b = True
    
    # Determine current candidate x
    candidates = []
    if valid_a:
        candidates.append(x_a)
    if valid_b:
        candidates.append(x_b)
    if not candidates:
        continue
    current_x = max(candidates)
    
    # Update p_max and x_max
    if p > p_max:
        p_max = p
        x_max = current_x
    elif p == p_max:
        if current_x > x_max:
            x_max = current_x

print(x_max)
0