2017年度「プログラミング言語1」「プログラミング言語演習」のページ

練習問題

2017年5月12日出題
  1. (ACM/ICPC 2008年日本国内予選問題B 改題)

    \(7\) で割った余りが \(1\) である正整数は \(7\mathbb{N}+1\) 数と呼ばれる。しかし,発音しにくいので,月曜数と呼ぼう。

    月曜数 \(a\), \(b\) に対して、月曜数 \(x\) が存在して \(ax=b\) が成り立つとき、\(a\) を \(b\) の月曜約数と呼ぶ。月曜数 \(a\) が月曜数 \(b\) の月曜約数であるためには、\(a\) が \(b\) の普通の意味の約数であれば必要十分であると、簡単に証明できる。

    \(1\) より大きな月曜数でそれ自身と \(1\) の他に月曜約数をもたないものを、月曜素数と呼ぶ。普通の意味の素数である月曜数は月曜素数であるが、逆は一般に成り立たない。たとえば,\(22\) は普通の意味の素数ではないが、月曜素数である。

    月曜数 \(a\) の月曜約数である月曜素数を、\(a\) の月曜素因数と呼ぶ。たとえば、\(22\) は月曜素数であり、\(10648=22\times484\) が成り立つので、 \(22\) は \(10648\) の月曜素因数のひとつである.

    \(1\) より大きなどんな月曜数も、1個以上の月曜素数の積として表すことができる。表し方は、順序の違いを無視しても、必ずしも一通りではない。たとえば、\(10648=8\times1331=22\times22\times22\) である。

    1. \(1048573\) 以下の月曜素数をすべて出力するプログラムを書け。

    2. \(8\) から \(1048573\) までの月曜数について月曜素因数の一覧表を出力するプログラムを書け。

      出力は、小さい月曜数から順に行うものとする。まず、月曜数を表示し,つづけて同じ行にコロン「:」、そして、月曜素因数の並びを、それぞれの前に空白を置いて、小さい順に重複なく表示する。該当の月曜数を複数回割る月曜素因数も1回だけ出力する。

      たとえば、\(10648\) に対しては、次のように出力する。

      10648: 8 22 1331
      	    
      補足1
      最初、上限として\(1048576\)を採用していましたが、この数は月曜数ではないので、それ以下の最大の月曜数\(1048573\)に書き換えました。問題は本質的には変わりません。

戻る
奈良女子大学生活環境学部情報衣環境学科生活情報通信科学コース