Рубрики
Без рубрики

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

См.Различные способы генерации простых чисел в Java.

Автор оригинала: baeldung.

1. введение

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

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

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

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

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

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

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

3.1. Java 7 и ранее – Грубая сила

public static List primeNumbersBruteForce(int n) {
    List 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;
}

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

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

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

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

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

Давайте посмотрим на условие в методе is Prime Brute Force () .

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

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

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

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

public static List primeNumbersBruteForce(int n) {
    List 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 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, …, н)
  2. Первоначально пусть p равно 2, первому простому числу
  3. Начиная с p , подсчитайте с шагом p и отметьте каждое из этих чисел больше, чем p само по себе в списке. Эти числа будут 2p, 3p, 4p и т. Д.; Обратите внимание, что некоторые из них, возможно, уже были отмечены
  4. Найдите первое число, большее p в списке, которое не помечено. Если такого номера не было, остановитесь. В противном случае пусть p теперь равно этому числу (которое является следующим простым числом) и повторите с шага 3

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

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

public static List 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 primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}

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

Давайте посмотрим, как это работает.

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

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

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

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

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

Читайте ещё по теме: