проблема

В этом проекте вы напишите Java-программу, которая считывает положительное целое число n из стандартного ввода, а затем печатает первые n простых чисел. Мы говорим, что целое число m делится на ненулевое целое число d, если существует такое целое число k, что m = k d, т.е. если d делится равномерно на m. Эквивалентно, m делится на d, если остаток от m после (целочисленного) деления на d равен нулю. Мы также выразили бы это, сказав, что d является делителем числа m. Целое положительное число p называется простым, если его единственными положительными делителями являются 1 и p. Единственным исключением из этого правила является само число 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 и т. Д. Если в любой точке найдется, что она делится на число d в диапазоне 2 d m − 1, то остановите и сделайте вывод, что m является составным. В противном случае заключите, что m простое число. Мгновенная мысль показывает, что не нужно делать пробных делений на числа d, которые сами по себе составные. Например, если пробное деление на 2 не удается (т. Е. Имеет ненулевой остаток, поэтому m нечетно), то пробное деление на 4, 6 или 8 или любое четное число также должно завершиться неудачей. Таким образом, чтобы проверить число m на простоту, нужно только пробное деление на простые числа, меньшие m. Кроме того, нет необходимости проходить весь путь до m − 1. Нужно только сделать пробные деления m на простые числа p в диапазоне 2 p m. Чтобы увидеть это, предположим, что m> 1 является составным. Тогда существуют натуральные числа a и b, такие что 1 <a <m, 1 <b <m и m = ab. Но если и a> m, и b> m, то ab> m, что противоречит тому, что m = ab. Следовательно, один из a или b должен быть меньше или равен m.

Чтобы реализовать этот процесс в Java, вы напишите функцию isPrime () со следующей сигнатурой:

static boolean isPrime(int m, int[] P) 

Эта функция будет возвращать true или false в зависимости от того, является ли m простым или составным. Аргумент массива P будет содержать достаточное количество простых чисел для тестирования. В частности, во время вызова isPrime () массив P должен содержать (как минимум) все простые числа p в диапазоне 2 p m. Например, чтобы проверить m = 53 на простоту, нужно выполнить последовательные пробные деления на 2, 3, 5 и 7. Мы не идем дальше, так как 11> 53. Таким образом, предварительным условием для вызова функции isPrime (53, P) является то, что P [0] = 2, P [1] = 3, P [2] = 5 и P [3] = 7. Возвращаемое значение в этом случае будет истинным, поскольку все эти деления не пройдены. Аналогично тесту 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. Функция isPrime () должна содержать цикл, проходящий через массив P и делающий пробные деления. Этот цикл должен завершаться, когда 2 либо пробное деление завершается успешно, в этом случае возвращается false, либо до тех пор, пока следующее простое число в P не станет больше m, и в этом случае будет возвращено true. Функция main () в этом проекте будет читать аргумент командной строки n, выделять массив int длины n, заполнять массив простыми числами, а затем печатать содержимое массива в стандартный вывод в соответствии с форматом, описанным ниже. В контексте функции main () мы будем ссылаться на этот массив как Primes []. Таким образом, массив Primes [] играет двойную роль в этом проекте. С одной стороны, он используется для сбора, хранения и печати выходных данных. С другой стороны, он передается функции isPrime () для проверки новых целых чисел на простоту. Всякий раз, когда isPrime () возвращает true, вновь обнаруженное простое число будет помещено в соответствующую позицию в массиве Primes []. Этот процесс работает, поскольку, как объяснено выше, простые числа, необходимые для проверки целочисленного диапазона m только до m, и все эти простые числа (и более) уже будут сохранены в массиве Primes [] при тестировании m. Конечно, необходимо будет инициализировать Primes [0] = 2 вручную, а затем перейти к проверке 3, 4, ... на простоту с помощью функции isPrime ().

Ниже приведен план шагов, которые необходимо выполнить в функции main ().

Убедитесь, что пользователь указал ровно один аргумент командной строки, который можно интерпретировать как положительное целое число n. Если аргумент командной строки не является одним положительным целым числом, ваша программа напечатает сообщение об использовании, как указано в примерах ниже, а затем завершится.Выделите массив простых чисел [] длины n и инициализируйте простые числа [0] = 2.Введите цикл, который обнаружит последующие простые числа и сохранит их как простые числа [1], простые числа [2], простые числа [3], ..., простые числа [n − 1]. Этот цикл должен содержать внутренний цикл, который проходит через последовательные целые числа и проверяет их на простоту, вызывая функцию isPrime () с соответствующими аргументами.Выведите содержимое массива Primes [] в stdout, 10 в строку, разделенную пробелами. Другими словами, простые числа от [0] до простых чисел [9] перейдут в строку 1, простые числа [10], хотя простые числа [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 (). Каждому из них должен предшествовать блок комментария с указанием его имени, краткого описания его работы и любых необходимых предварительных условий (например, для isPrime ()). См. Примеры на веб-странице.

Попытка решения

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));
    }
}