課題 A-4

問題

2 以上 1000000 未満の整数を読み込み, それが素数であるかどうかを判定するプログラムを作りなさい.

※ 2 以上の整数 x が与えられたとき, x が 2 以上 x 未満のいずれの数でも割りきれなければ x は素数である.
(採点ポイント) まともに割り算を繰り返すよりも何らかの工夫により計算回数を減らす方が望ましい.
 

入力データと出力例

  • 2 → 素数
  • 999999 → 素数でない
  • 9973 → 素数
  • 5077 → 素数
  • 773 → 素数
  • 19973 → 素数
  • 29973 → 素数でない

(C) 2006 Hirohisa AMAN <aman@cs.ehime-u.ac.jp, aman@computer.org>