結果

問題 No.1058 素敵な数
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:16:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 1,187 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 60,252 KB
最終ジャッジ日時 2025-03-20 21:16:57
合計ジャッジ時間 1,153 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    max_divisor = math.isqrt(x) + 1
    for i in range(3, max_divisor, 2):
        if x % i == 0:
            return False
    return True

def generate_large_primes(start, count):
    primes = []
    current = start
    if current % 2 == 0:
        current += 1
    while len(primes) < count:
        if is_prime(current):
            primes.append(current)
        current += 2
    return primes

# Generate the first 20 primes greater than 1e5
primes = generate_large_primes(10**5 + 1, 20)

candidates = []

# Generate all possible products of primes where i <= j
for i in range(len(primes)):
    p_i = primes[i]
    # Add the square
    candidates.append(p_i * p_i)
    # Add products with all primes[j] where j > i
    for j in range(i + 1, len(primes)):
        p_j = primes[j]
        candidates.append(p_i * p_j)

# Remove duplicates and sort
candidates = sorted(list(set(candidates)))

# The suteki numbers list starts with 1 followed by the sorted candidates
suteki_numbers = [1] + candidates

N = int(input())
print(suteki_numbers[N-1])
0