«1. Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Давайте посмотрим на шаги этого алгоритма:

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

  1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n)
  2. Initially, let p be equal 2, the first prime number
  3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked
  4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3

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

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

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

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

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

4. Заключение

  1. The loop starts with 2, so we leave 2 unmarked and mark all the divisors of 2. It’s marked in image with the red color
  2. The loop moves to 3, so we leave 3 unmarked and mark all the divisors of 3 not already marked. It’s marked in image with the green color
  3. Loop moves to 4, it’s already marked, so we continue
  4. Loop moves to 5, so we leave 5 unmarked and mark all the divisors of 5 not already marked. It’s marked in image with the purple color
  5. We continue above steps until loop is reached equal to square root of n

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

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

«