BOJ 6588:キムバッハ予想

20585 ワード
boj テキストリンク

ソース:https://www.acmicpc.net/problem/6588


質問する


1742年、ドイツのアマチュア数学者クリスティアン・ゴルドバッハはレオン・ハトオラーに手紙を書いて、以下の推測を提案した.
4より大きいすべての偶数は、2つの奇数小数の和として表すことができる.
例えば、8は3+5と表すことができ、3と5はいずれも奇数の小数である.また、20=3+17=7+13、42=5+37=11+31=13+29=19+23となる.
この推測はまだ未解決の問題だ...
100万以下のすべての偶数について、この推測を検証するプログラムを作成してください.

入力


入力は、1つ以上のテストケースで構成されます.テストボックスの数は100000個を超えない.
各試験箱は偶数整数nからなる.(6 ≤ n ≤ 1000000)
入力した最後の行にはゼロが表示されます.

しゅつりょく


入力は、1つ以上のテストケースで構成されます.テストボックスの数は100000個を超えない.
各試験箱は偶数整数nからなる.(6 ≤ n ≤ 1000000)
入力した最後の行にはゼロが表示されます.

アイデア


Inputnumberより小さいすべての小数をリスト化し,組合せを用いて金バッハ推定を行った.

コード#コード#



Mine 1(タイムアウト)

import sys
from itertools import combinations

def primeNum(a):
    if a == 1:
        return False
    for i in range(2, a):
        if a%i == 0:
            return False
    return True

data = True
while data:
    data = int(input())
    datas = []
    ans = (0,0)
    for j in range(1, data, 2):
        if primeNum(j) == True:
            datas.append(j)
    for case in combinations(datas,2):
        if sum(case) == data:
            if (ans[1]-ans[0]) < (case[1]-case[0]):
                ans = case
    if ans == (0,0):
        print("Goldbach's conjecture is wrong.")
    else:
        print(data,'=',ans[0],'+',ans[1],sep=' ')

Mine 2(タイムアウト)

Max = 1000000
prime = [False for i in range(Max+1)]

for i in range(2, Max+1):
    if i*i > Max:
        break
    if prime[i] is False:
        for j in range(i*i, Max+1, i):
            prime[j] = True

data = True
while data:
    data = int(input())
    ans = [0,0]
    for i in range(2, Max+1):
        if prime[i] == False:
            j = data - i
            if prime[j] == False:
                if ans[1] < j:
                    ans = [i,j]
    if ans == [0, 0]:
        print("Goldbach's conjecture is wrong.")
    else:
        print(data, '=', ans[0], '+', ans[1], sep=' ')

Mine 3(タイムアウト)

def primeNum(a):
    if a == 1:
        return False
    for i in range(2, a):
        if a%i == 0:
            return False
    return True

def goldBach(n):
    for i in range(3, n, 2):
        if primeNum(i) and primeNum(n-i):
            return i
    return -1

data = True
while data:
    data = int(input())
    gold = goldBach(data)
    if gold == -1:
        print("Goldbach's conjecture is wrong.")
    else:
        print('{} = {} + {}'.format(data,gold,data-gold))

Solution


ソース:https://velog.io/@daythoe 0/BaekJoon-6588-ゴールドバッハの-推測
import sys

def isPrime(a):

    i=3
    while i*i <=a:
        if a%i==0 : return False
        else: i+=2
    return True

def goldBach(n):

    for i in range(3,n//2+1,2):
        if isPrime(i) and isPrime(n-i):
            return i
    return -1

while True:
    a = int(sys.stdin.readline())
    if a ==0 : break

    gold = goldBach(a)
    if(gold == -1):
        print("Goldbach's conjecture is wrong.")
    else:
        print("{} = {} + {}".format(a,gold,a-gold))

改善

  • の少数リストを「エラトステネスの体」として再確認する必要がある.
    • Sysは
  • int(input)より大きい.stdin.readline()
    • の使用
    [Assignment]3赤レンガ
    [MSDN]sprintf, swprintf