>* не будут вычеркнуты все кратные.
>*/
>public class PrimeGenerator
>{
> private static boolean[] crossedOut;
> private static int[] result;
> public static int[] generatePrimes(int maxValue)
> {
> if (maxValue < 2)
> return new int[0];
> else
> {
> uncrossIntegersUpTo(maxValue);
> crossOutMultiples();
> putUncrossedIntegersIntoResult();
> return result;
> }
> }
> private static void uncrossIntegersUpTo(int maxValue)
> {
> crossedOut = new boolean[maxValue + 1];
> for (int i = 2; i < crossedOut.length; i++)
> crossedOut[i] = false;
> }
> private static void crossOutMultiples()
> {
> int limit = determineIterationLimit();
> for (int i = 2; i <= limit; i++)
> if (notCrossed(i))
> crossOutMultiplesOf(i);
> }
> private static int determineIterationLimit()
> {
> // Каждое кратное в массиве имеет простой множитель, больший либо равный
> // квадратному корню из размера массива. Следовательно, вычеркивать элементы,
> // кратные числам, превышающих квадратный корень, не нужно.
> double iterationLimit = Math.sqrt(crossedOut.length);
> return (int) iterationLimit;
> }
> private static void crossOutMultiplesOf(int i)
> {
> for (int multiple = 2*i;
> multiple < crossedOut.length;
> multiple += i)
> crossedOut[multiple] = true;
> }
> private static boolean notCrossed(int i)
> {
> return crossedOut[i] == false;
> }
> private static void putUncrossedIntegersIntoResult()
> {
> result = new int[numberOfUncrossedIntegers()];
> for (int j = 0, i = 2; i < crossedOut.length; i++)
> if (notCrossed(i))
> result[j++] = i;
> }
> private static int numberOfUncrossedIntegers()
> {
> int count = 0;
> for (int i = 2; i < crossedOut.length; i++)
> if (notCrossed(i))
> count++;
> return count;
> }
>}
Можно возразить, что первый комментарий избыточен, потому что он практически полностью повторяет код самой функции generatePrimes. И все же я считаю, что этот комментарий упрощает понимание алгоритма пользователем, поэтому я склонен оставить его.
Второй комментарий почти стопроцентно необходим. Он объясняет смысл использования квадратного корня как верхней границы цикла. Мне не удалось найти ни простого имени переменной, ни другой структуры кода, которые бы наглядно передавали это обстоятельство. С другой стороны, само использование квадратного корня может быть иллюзией. Действительно ли ограничение цикла квадратным корнем способно сэкономить время? Не уйдет ли на его вычисление больше времени, чем я экономлю? Об этом стоит подумать. Использование квадратного корня в качестве верхней границы цикла тешит мои наклонности старого хакера, работавшего на C и ассемблере, но я не уверен, что оно оправдает время и усилия, необходимые читателям кода для его понимания.