1. paizaラーニングトップ
  2. レベルアップ問題集
  3. 素数メニュー(言語選択)
  4. 問題一覧
  5. ゴールドバッハ予想

素数メニューのサムネイル
ゴールドバッハ予想(paizaランク C 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

素数に関連した数学の有名な未解決問題としてゴールドバッハ予想があります。その内容は次の通りです。
「全ての 3 よりも大きな偶数は 2 つの素数の和として表すことができる。」
全ての 3 よりも大きな偶数に対応する 2 つの素数が存在するかどうかはコンピュータを持ってしても確かめることができませんが、ある程度の大きさの数までならコンピュータで対応する 2 つの素数を求めることができます。
実際に 4 × 10^18 まではゴールドバッハ予想が成立することは証明されています。
そこで、10^5 以下の偶数 N が与えられるので、 N を 2 つの素数の和で表し、出力してください。
ただし、答えが複数個ある場合は、それらのうち、積が最も大きくなるような 2 つの素数を出力してください。(答えは 1 通りになることが保証されます。)

入力される値

N


・ 1 行で整数 N が与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

足して N となる 2 つの素数のうち、積が最大であるものを小さい素数から順に改行区切りで 2 行で出力してください。
出力の末尾には改行を入れてください。

条件

・ 4 ≦ N ≦ 100,000
・ N は偶数である

入力例1

4

出力例1

2
2

入力例2

108

出力例2

47
61

問題一覧へ戻る

ページの先頭へ戻る