TIL)9020金バッハ推測

🧵 アラトスの体

これは少数を求める最も効率的な方法です.
💡 アイデア

の数に従ってアレイを予めTrue/Felseに初期化し、

.

2から終わりまで、2の倍数、3の倍数、4の倍数・・抹消羅鑑

eratos = [1] * 10001
eratos[0] = 0
eratos[1] = 0

for i in range(2, 10000):
    if eratos[i] == 1:
        j = 2 # j는 2부터 시작
        while i*j <= 10000:
            eratos[i*j] = 0
            j += 1

🧶 キムバッハの推測

エラトスの体を利用して解決した問題.
数字を入力すると、ラトスのふるいで少数であれば条件を満たして出力します.

eratos = [1] * 10001
eratos[0] = 0
eratos[1] = 0

for i in range(2, 10000):
    if eratos[i] == 1:
        j = 2 # j는 2부터 시작
        while i*j <= 10000:
            eratos[i*j] = 0
            j += 1

# N을 입력받음
N = int(input())

for i in range(0, N):
    num = int(input())
    num1 = -1
    num2 = -1
    # 절반의 숫자만 반복
    for j in range(2, int(num//2)+1):
        if eratos[j] and eratos[num-j]:
            num1 = j
            num2 = num-j
    print(num1, num2)