Задача
В этом проекте вы напишите Java-программу, которая читает стандартное входное значение n, а затем
печатает первые n простых чисел. Мы говорим, что целое число m делится на ненулевое целое число d, если есть
существует целое число k такое, что m = k d, т.е. если d делится равномерно на m. Эквивалентно, m делится на d, если
остаток от m при (целочисленном) делении на d равен нулю. Мы также выразили бы это, сказав, что d является
делитель м. Целое положительное число 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 и т. д. Если окажется, что в любой точке m делится на число d в диапазоне 2 d m − 1, то
остановить и сделать вывод, что т является составным. В противном случае заключите, что m простое число. Минутная мысль показывает
что не нужно делать пробных делений на числа d, которые сами по себе составные. Например, если
пробное деление на 2 не выполняется (т. е. имеет ненулевой остаток, поэтому m нечетно), затем пробное деление на 4, 6 или 8, или любое
четное число, также должно выйти из строя. Таким образом, чтобы проверить число m на простоту, нужно только сделать пробное деление на
простые числа меньше м. Кроме того, нет необходимости проходить весь путь до m − 1. Нужно только одно
сделать пробные деления m на простые числа p в диапазоне 2 p m. Чтобы увидеть это, предположим, что m> 1 является составным.
Тогда существуют натуральные числа a и b, такие что 1 m и b> m, то ab> m, что противоречит тому, что m = ab. Следовательно, один из a или b должен быть меньше
или равно м.
Чтобы реализовать этот процесс в 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, недавно обнаруженное простое число будет помещено в соответствующую позицию в массиве
Штрихи[]. Этот процесс работает, поскольку, как объяснено выше, простые числа необходимы для проверки целочисленного диапазона m
только до m, и все эти простые числа (и более) будут уже сохранены в массиве Primes [], когда m
испытания. Конечно, необходимо вручную инициализировать простые числа [0] = 2, а затем перейти к тесту 3, 4,…
для простоты используем функцию isPrime ().
Ниже приведен план действий, выполняемых в функции main ().
- Убедитесь, что пользователь указал ровно один аргумент командной строки, который можно интерпретировать как
положительное целое число n. Если аргумент командной строки не является одним положительным целым числом, ваша программа
напечатает сообщение об использовании, как указано в примерах ниже, а затем выйдет.
- Выделите простые числа [] массива n и инициализируйте простые числа [0] = 2.
- Введите цикл, который обнаружит последующие простые числа и сохранит их как простые числа [1], простые числа [2],
Простые числа [3], ..., простые числа [n − 1]. Этот цикл должен содержать внутренний цикл, который проходит через
последовательные целые и проверяют их на простоту, вызывая функцию isPrime () с соответствующим
аргументы.
- Вывести содержимое массива Primes [] в стандартный вывод, 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));
}
}