Задачи на простые алгоритмы о простых числах

class Algorithms

1. boolean[] sieveOfEratosthenes(int n) Реализуйте решето эратосфена. Прочитайте алгоритм, реализуйте функцию, которая по заданному n возвращает простые числа, не превосходящие n. Для реализации заведите массив boolean[] prime размера $n + 1$, чтобы prime[i] хранило, является ли число $i$ простым. Верните этот массив.
2. int[] primes(int n) Напишите еще одну функцию, которая делает то же самое, но конце возвращает новый массив int[] уже только из простых чисел.

3. Дано число $n$. Разложите это число на простые множители, верните результат в виде двумерного массива из простых чисел и их степеней. Например, для числа $600=2^33^15^2$ необходимо вернуть массив { {2,3}, {3, 1}, {5,2} }.

   Реализуйте следующий алгоритм разложения. Перебирайте делители $d$, начиная с 2. После этого $d$ должен либо увеличиваться на 1 ($d=2,3,4,5,6,\ldots$), либо, если вы решили предыдущую задачу, он должен перебирать простые числа ($d=2,3,5,7,11,\ldots$). Пробуйте делить $n$ на каждый $d$, причём делите, пока делится. Например, при делении 600 на 2 вы должны получить сначала 300, потом 150, потом 75. $n$ при каждом делении уменьшается, а вы сохраняете степень делителя, т.е. сколько раз пришлось поделить на d (в примере — 3 раза). Перебор останавливается, когда $d^2 > n$. Если $n$ не равен 1, то он тоже попадает в ответ.

   Рассмотрим для примера число 56. Сначала мы делим 56 на $d=2$ три раза, получаем $n=7$. Пробуем делить на $d=3$, но $d^2>n=7$, поэтому перебор останавливается, и в ответ записывается еще число 7 в первой степени.

   В этой задаче неудобно пользоваться массивом для наполнения ответа, список будет проще.

4. На отдельной странице Задача о бинарном поиске.