Генерация простых чисел в Java

1. Введение

В этом руководстве мы покажем различные способы генерации простых чисел с помощью Java.

Если вы хотите проверить, является ли число простым, вот краткое руководство о том, как это сделать.

2. Простые числа

Начнем с основного определения. Простое число — это натуральное число больше единицы, которое не имеет положительных делителей, кроме единицы и самого себя.

Например, число 7 простое, потому что 1 и 7 — его единственные положительные целые делители, а число 12 — нет, потому что оно имеет делители 3 и 2 в дополнение к 1, 4 и 6.

3. Генерация простых чисел

В этом разделе мы увидим, как можно эффективно генерировать простые числа, которые меньше заданного значения.

3.1. Java 7 и ранее — грубая сила

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
public static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Как видите, PrimeNumbersBruteForce перебирает числа от 2 до n и просто вызывает метод isPrimeBruteForce() , чтобы проверить, является число простым или нет.

Метод проверяет делимость каждого числа на числа в диапазоне от 2 до числа-1 .

Если в какой-то момент мы встретим число, которое делится, мы вернем false. В конце, когда мы обнаруживаем, что это число не делится ни на одно из своих предыдущих чисел, мы возвращаем true, указывая на то, что это простое число.

3.2. Эффективность и оптимизация

Предыдущий алгоритм не является линейным и имеет временную сложность O(n^2). Алгоритм также неэффективен, и явно есть место для улучшения.

Давайте посмотрим на условие в методе isPrimeBruteForce() .

Когда число не является простым, это число можно разложить на два множителя, а именно a и b , т.е. число = a b. **Если бы и a, и b были больше квадратного корня из n , `то ab было бы больше, чем n` .**

Таким образом, по крайней мере один из этих факторов должен быть меньше или равен квадратному корню из числа, и чтобы проверить, является ли число простым, нам нужно только проверить факторы, меньшие или равные квадратному корню из проверяемого числа.

Кроме того, простые числа никогда не могут быть четными, поскольку все четные числа делятся на 2.

Имея в виду вышеизложенные идеи, давайте улучшим алгоритм:

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    if (n >= 2) {
        primeNumbers.add(2);
    }
    for (int i = 3; i <= n; i += 2) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
private static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i*i <= number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

3.3. Использование Java 8

Давайте посмотрим, как мы можем переписать предыдущее решение, используя идиомы Java 8:

public static List<Integer> primeNumbersTill(int n) {
    return IntStream.rangeClosed(2, n)
      .filter(x -> isPrime(x)).boxed()
      .collect(Collectors.toList());
}
private static boolean isPrime(int number) {
    return IntStream.rangeClosed(2, (int) (Math.sqrt(number)))
      .allMatch(n -> x % n != 0);
}

3.4. Использование сита Эратосфена

Есть еще один эффективный метод, который может помочь нам эффективно генерировать простые числа, и он называется «Решето Эратосфена». Его временная эффективность составляет O (n logn).

Рассмотрим шаги этого алгоритма:

1. Создайте список последовательных целых чисел от 2 до n : (2, 3, 4, …, n)
2. Первоначально пусть p равно 2, первое простое число
3. Начиная с p , посчитайте с шагом p и отметьте каждое из этих чисел больше самого p в списке. Эти числа будут 2р, 3р, 4р и т.д.; обратите внимание, что некоторые из них, возможно, уже были отмечены
4. Найдите в списке первое число, большее p , которое не отмечено. Если такого номера не было, остановитесь. В противном случае пусть p теперь равно этому числу (которое является следующим простым числом) и повторяется с шага 3.

В конце, когда алгоритм завершает работу, все числа в списке, которые не отмечены, являются простыми числами.

Вот как выглядит код:

public static List<Integer> sieveOfEratosthenes(int n) {
    boolean prime[] = new boolean[n + 1];
    Arrays.fill(prime, true);
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}

3.5. Рабочий пример сита Эратосфена

Давайте посмотрим, как это работает для n=30.

Рассмотрим изображение выше, вот проходы, сделанные алгоритмом:

1. Цикл начинается с 2, поэтому мы оставляем 2 неотмеченными и отмечаем все делители 2. На изображении он отмечен красным цветом.
2. Цикл перемещается к 3, поэтому мы оставляем 3 неотмеченными и отмечаем все делители 3, которые еще не отмечены. Он отмечен на изображении зеленым цветом
3. Цикл перемещается на 4, он уже отмечен, поэтому мы продолжаем
4. Цикл перемещается к 5, поэтому мы оставляем 5 неотмеченными и отмечаем все делители 5, которые еще не отмечены. Он отмечен на изображении фиолетовым цветом
5. Мы продолжаем описанные выше шаги, пока не будет достигнута петля, равная квадратному корню из n .

4. Вывод

В этом кратком руководстве мы проиллюстрировали, как мы можем генерировать простые числа до значения «N».

Реализацию этих примеров можно найти на GitHub .