問題
このプロジェクトでは、標準入力から正の整数nを読み取り、最初のn個の素数を出力するJavaプログラムを作成します。m = kdのような整数kが存在する場合、つまりdがmに均等に分割される場合、整数mは非ゼロの整数dで割り切れると言います。同様に、dによる(整数の)除算の余りがゼロの場合、mはdで割り切れます。また、dはmの約数であると言うことでこれを表現します。正の整数pは、その正の約数が1とpのみである場合、素数と呼ばれます。この規則の1つの例外は、素数ではないと見なされる1番自体です。素数ではない正の整数は、合成と呼ばれます。ユークリッドは、素数が無限に多いことを示しました。プライムシーケンスとコンポジットシーケンスは次のように始まります。
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
Composites: 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, …
素数性について数をテストする方法はたくさんありますが、おそらく最も簡単なのは、単純に試行分割を行うことです。mを2で割ることから始めます。均等に割る場合、mは素数ではありません。それ以外の場合は、3、次に4、次に5などで除算します。任意の点でmが2 dm-1の範囲の数値dで割り切れることがわかった場合は、停止し、mが複合であると結論付けます。それ以外の場合は、mが素数であると結論付けます。一瞬の考えは、それ自体が複合である数dによる試行除算を行う必要がないことを示しています。たとえば、2による試行除算が失敗した場合(つまり、余りがゼロ以外であるため、mが奇数)、4、6、8、または任意の偶数による試行除算も失敗する必要があります。したがって、素数mについて素数をテストするには、m未満の素数で試行除算を行うだけで済みます。さらに、m-1まで行く必要はありません。午後2時の範囲で素数pによるmの試行除算を行うだけで済みます。これを確認するために、m>1が合成であると仮定します。次に、1 <a <m、1 <b <m、およびm=abとなる正の整数aおよびbが存在します。しかし、a>mとb>mの両方の場合、ab> mであり、m=abと矛盾します。したがって、aまたはbのいずれかがm以下である必要があります。
このプロセスをJavaで実装するには、次のシグネチャを使用してisPrime()という関数を記述します。
static boolean isPrime(int m, int[] P)
この関数は、mが素数であるか合成であるかに応じて、trueまたはfalseを返します。配列引数Pには、テストを実行するのに十分な数の素数が含まれます。具体的には、isPrime()が呼び出された時点で、配列Pには(少なくとも)午後2時の範囲のすべての素数pが含まれている必要があります。たとえば、素数性についてm = 53をテストするには、2、3、5、および7で連続した試行除算を実行する必要があります。11>53以降はこれ以上進みません。したがって、関数呼び出しisPrime(53、P)の前提条件は、P [0] = 2、P [1] = 3、P [2] = 5、およびP [3]=7です。これらのすべての除算が失敗するため、この場合の戻り値はtrueになります。m = 143をテストするのと同様に、2、3、5、7、および11で試行除算を行う必要があります(13> 143であるため)。したがって、関数呼び出しisPrime(143、P)の前提条件は、P [0] = 2、P [1] = 3、P [2] = 5、P [3] = 7、およびP [4]=11です。この場合の戻り値は、11が143を除算するため、falseになります。関数isPrime()には、配列Pをステップスルーし、試行除算を実行するループが含まれている必要があります。このループは、試行除算が成功した場合(falseが返される場合)、またはPの次の素数がmより大きい場合(trueが返される場合)に終了する必要があります。このプロジェクトの関数main()は、コマンドライン引数nを読み取り、長さnのint配列を割り当て、配列を素数で埋めてから、以下に説明する形式に従って配列の内容をstdoutに出力します。関数main()のコンテキストでは、この配列をPrimes[]と呼びます。したがって、アレイPrimes[]はこのプロジェクトで2つの役割を果たします。一方では、出力データを収集、保存、および印刷するために使用されます。一方で、これは関数isPrime()に渡され、新しい整数の素数性をテストします。isPrime()がtrueを返すときはいつでも、新しく検出された素数は配列Primes[]の適切な位置に配置されます。上で説明したように、mまでの整数mの範囲をテストするために必要な素数は、mがテストされるときに、これらすべての素数(およびそれ以上)が配列Primes []にすでに格納されているため、このプロセスは機能します。もちろん、Primes [0] = 2を手動で初期化してから、関数isPrime()を使用して素数性のテスト3、4、…に進む必要があります。mがテストされると、これらすべての素数(およびそれ以上)はすでに配列Primes[]に格納されます。もちろん、Primes [0] = 2を手動で初期化してから、関数isPrime()を使用して素数性のテスト3、4、…に進む必要があります。mがテストされると、これらすべての素数(およびそれ以上)はすでに配列Primes[]に格納されます。もちろん、Primes [0] = 2を手動で初期化してから、関数isPrime()を使用して素数性のテスト3、4、…に進む必要があります。
以下は、関数main()で実行される手順の概要です。
- ユーザーが正の整数nとして解釈できるコマンドライン引数を1つだけ指定したことを確認してください。コマンドライン引数が単一の正の整数でない場合、プログラムは以下の例で指定されているように使用法メッセージを出力してから終了します。
- 長さnの配列Primes[]を割り当て、Primes [0]=2を初期化します。
- 後続の素数を検出し、それらをPrimes [1]、Primes [2]、Primes [3]、...、Primes[n-1]として格納するループに入ります。このループには、連続する整数をウォークスルーし、適切な引数を指定して関数isPrime()を呼び出すことにより、それらの素数性をテストする内部ループが含まれている必要があります。
- 配列Primes[]の内容をstdoutに出力し、10を単一スペースで区切られた行に出力します。つまり、Primes[0]からPrimes[9]は1行目になり、Primes[10]はPrimes[19]は2行目になります。nが10の倍数でない場合、出力の最後の行には10未満の素数が含まれることに注意してください。
Prime.javaと呼ばれるプログラムは、以下のサンプル実行と同じ出力を生成します。(いつものように、%はunixプロンプトを意味します。)
% java Prime
Usage: java Prime [PositiveInteger]
% java Prime xyz
Usage: java Prime [PositiveInteger]
% java Prime 10 20
Usage: java Prime [PositiveInteger]
% java Prime 75
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379
%
3
ご覧のとおり、不適切なコマンドライン引数は、多くのUNIXコマンドと同様の使用法メッセージを生成します。(このようなメッセージを表示するには、引数なしでmoreコマンドを実行してみてください。)プログラムには、署名を持つUsage()という関数が含まれます。
static void Usage()
このメッセージをstderrに出力してから、終了します。したがって、プログラムには、main()、isPrime()、Usage()の3つの関数が含まれます。それぞれの前に、名前、操作の簡単な説明、および必要な前提条件(isPrime()など)を示すコメントブロックを付ける必要があります。Webページの例を参照してください。
試みられた解決策
class Prime {
public static void main(String[] args) {
int num1 = 0;
int num2 = 0;
int num3;
for (num1 = 1; num1 < 101; num1++)
System.out.println(num1);
for (num2 = 1; num2 < 101; num1++)
System.out.println(num2);
num3 = num2 % num1;
if (num3 == 0)
System.out.println("The prime numbers are " + num1);
else
System.out.println("The prime numbers are " + (num1 += 1));
}
}