問題一覧 > 教育的問題

No.3030 ミラー・ラビン素数判定法のテスト

レベル : / 実行時間制限 : 1ケース 9.973秒 / メモリ制限 : 509 MB / 通常問題
タグ : / 解いたユーザー数 72
作問者 : yuppe19 😺yuppe19 😺
7 ProblemId : 1967
問題文最終更新日: 2019-03-11 11:24:51

問題文

与えられた $n$ 個の正整数それぞれについて、それが素数かどうかを判定してください。

入力

$n$
$x_{0}$
$x_{1}$
...
$x_{n-1}$

一行目はクエリの数 $n$ です。
二行目以降は素数判定すべき $n$ 個の正整数です。
・$n$ は正整数。
・$1 \le n \le 10{,}000$
・$1 \le x_{i} \lt 2^{63}$ (64ビット符号つき整数に収まります)

出力

正整数のそれぞれについて、
その値と素数か否か(素数なら 1 そうでないなら 0)を半角空白区切りで、入力順を維持したまま出力し、改行してください。

サンプル

入力
4
10
2
1
5
出力
10 0
2 1
1 0
5 1

一行目が 4 なので、4 個の正整数について素数判定することになります。
10 や 1 は素数ではないので、数自身と空白に加えて 0 を出力し、
2 や 5 は素数なので 1 を出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。