Как найти все простые числа java

Простое число – это число, которое делится нацело без остатка только на 1 и на самого себя. Также известно, что любое целое число, большее 1, является либо простым, либо может быть выражено как произведение простых чисел. Ряд простых чисел начинается с 2 и имеет следующий вид: 2, 3, 5, 7 и т.д.

Рассмотрим алгоритм поиска простых чисел, известный как «метод перебора делителей». Для этого давайте реализуем на Java метод getFirstPrimes(), который будет возвращать N первых простых чисел.

public List<Integer> getFirstPrimes(int count) {
    List<Integer> primes = new ArrayList<>();
    if (count > 0) {
        primes.add(2);
    }
    for (var i = 3; primes.size() < count; i += 2) {
        if (isPrime(i, primes)) {
            primes.add(i);
        }
    }
    return primes;
}

Все найденные простые числа будем складывать в список. Далее проверяем, что если у нас запросили хотя бы одно простое число, то сразу добавим 2, т.к. с него начинается последовательность. Далее в цикле начинаем проверять числа, сразу начиная с трёх. Также обратите внимание, что мы проверяем только нечётные числа (приращение +2), т.к. все чётные числа по определению делятся на 2.

Цикл выполняется до тех пор, пока в нашем результирующем списке не окажется ровно столько простых чисел, сколько у нас запросили. Саму проверку на «простоту» выполняем с помощью метода isPrime(), которому передаём текущее проверяемое число и уже накопленные нами на предыдущих итерациях числа.

private boolean isPrime(int n, List<Integer> primes) {
    double sqrt = Math.sqrt(n);
    for (var i = 0; i < primes.size(); i++) {
        var prime = primes.get(i);
        if (prime > sqrt) {
            return true;
        }
        if (n % prime == 0) {
            return false;
        }
    }
    return true;
}

Здесь мы сначала вызываем метод Math.sqrt(), ведь если проверяемое число состоит хотя бы из двух множителей, то ни одно из них не может превышать двоичный корень.

Затем в цикле проходим по всем уже найденным простым числам и по очереди пытаемся делить на них текущее число. Если число делится на простое число без остатка – значит, оно составное. Проверку выполняем до тех пор, пока простые числа меньше корня из проверяемого числа.

Можно выполнить небольшую оптимизацию, отказавшись от вычисления квадратного корня и операций над типом double. Вместо этого будем возводить каждое уже найденное простое число в квадрат и проверять, не превысило ли это произведение потенциально простое число. Если превысило, значит, перед нами новое простое число:

private boolean isPrime(int n, List<Integer> primes) {
    for (var i = 0; i < primes.size(); i++) {
        var prime = primes.get(i);
        if (prime * prime > n) {
            return true;
        }
        if (n % prime == 0) {
            return false;
        }
    }
    return true;
}

Рассмотренный алгоритм работает довольно быстро. За пару секунд он находит 500 000 простых чисел.

Оптимизации, которые мы применили:

• проверяем только нечётные числа
• пытаемся делить только на уже найденные простые числа
• делителями могут быть только те простые числа, которые не превосходят квадратного корня из проверяемого числа
• вместо вычисления квадратного корня возводим в квадрат каждое уже найденное простое число, пока произведение не превысит проверяемое число

Данный алгоритм хорошо подходит в том случае, если вам нужно ровно N первых простых чисел. Если же вы ищете все простые числа в некотором диапазоне, то лучше использовать Решето Эратосфена для поиска простых чисел – он будет работать гораздо быстрее.

Следующие примеры Java напечатают список всех простых чисел до 1000:

2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113	127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229	233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349	353	359	367	373	379	383	389	397	401	409
419	421	431	433	439	443	449	457	461	463	467	479	487	491	499	503	509	521	523	541
547	557	563	569	571	577	587	593	599	601	607	613	617	619	631	641	643	647	653	659
661	673	677	683	691	701	709	719	727	733	739	743	751	757	761	769	773	787	797	809
811	821	823	827	829	839	853	857	859	863	877	881	883	887	907	911	919	929	937	941
947	953	967	971	977	983	991	997

Total: 168

3 примера Java:

• Java 8 Stream и BigInteger
• Обычная старая Ява
• Алгоритм сита Эратосфена

1. Java 8 Stream и BigInteger

1.1 Использование Stream.

PrintPrimeNumber.java

package com.csharpcoderr.test;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class PrintPrimeNumber {

public static void main(String[] args) {

long count = Stream.iterate(0, n -> n + 1)
.limit(1000)
.filter(TestPrime::isPrime)
.peek(x -> System.out.format("%st", x))
.count();

System.out.println("nTotal: " + count);

}

public static boolean isPrime(int number) {

if (number <= 1) return false; // 1 не простое, а также не составное

return !IntStream.rangeClosed(2, number / 2).anyMatch(i -> number % i == 0);
}

}

1.2 Использование BigInteger::nextProbablePrime

Stream.iterate(BigInteger.valueOf(2), BigInteger::nextProbablePrime)
.limit(168)
.forEach(x -> System.out.format("%st", x));

Или же BigInteger.TWO для Java 9

Stream.iterate(BigInteger.TWO, BigInteger::nextProbablePrime)
.limit(168)
.forEach(x -> System.out.format("%st", x));

2. Обычная старая Ява

Нет больше Java 8 Stream, назад к основному.

PrintPrimeNumber2.java

package com.csharpcoderr.test;

import java.util.ArrayList;
import java.util.List;

public class PrintPrimeNumber2 {

public static void main(String[] args) {

List collect = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
if (isPrime(i)) {
collect.add(i);
}
}

for (Integer prime : collect) {
System.out.format("%st", prime);
}

System.out.println("nTotal: " + collect.size());

}

private static boolean isPrime(int number) {

if (number <= 1) return false;    // 1 не простое, а также не составное

for (int i = 2; i * i <= number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}

}

3. Сито Эратосфена

Этот алгоритм Sieve of Eratosthenes очень быстро находит все простые числа.

PS Изображение из Википедии

Концепция такова:

• Петля 1 # p=2 = true, следующие 4,6,8,10,12,14 … limit, all +2 set false
• Цикл 2 # p=3 = true, следующие 6 {false, 1 #, игнорировать}, 9,12 {false, 1 #, игнорировать}, 15,18 {false, 1 #, игнорировать}, 21 … предел, все +3 установлены false
• Петля 3 # p=4 = {ложь, 1 #, игнорировать}
• Петля 4 # p=5 = true, следующие 10 {false, 1 #, игнорировать}, 15 {false, 2 #, игнорировать}, 20 {false, 1 #, игнорировать} … все +5 установить false
• Петля 5 # p=6 = {ложь, 1 #, игнорировать}
• Цикл … до предела, та же идея.
• Соберите все true = простое число.

PrintPrimeNumber3

package com.csharpcoderr.test;

import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;

public class PrintPrimeNumber3 {

public static void main(String[] args) {

List result = primes_soe_array(1000);

result.forEach(x -> System.out.format("%st", x));

System.out.println("nTotal: " + result.size());

}

/**
* Sieve of Eratosthenes, true = prime number
*/
private static List primes_soe(int limit) {

BitSet primes = new BitSet(limit);
primes.set(0, false);
primes.set(1, false);
primes.set(2, limit, true);

for (int p = 2; p * p <= limit; p++) {
if (primes.get(p)) {
for (int j = p * 2; j <= limit; j += p) {
primes.set(j, false);
}
}
}

List result = new LinkedList<>();
for (int i = 0; i <= limit; i++) {
if (primes.get(i)) {
result.add(i);
}
}

return result;

}

// Некоторые разработчики предпочитают массив.
public static List primes_soe_array(int limit) {

boolean primes[] = new boolean[limit + 1];
Arrays.fill(primes, true);
primes[0] = false;
primes[1] = false;

for (int p = 2; p * p <= limit; p++) {
if (primes[p]) {
for (int j = p * 2; j <= limit; j += p) {
primes[j] = false;
}
}
}

List result = new LinkedList<>();
for (int i = 0; i <= limit; i++) {
if (primes[i]) {
result.add(i);
}
}
return result;
}

}

Кто-нибудь может помочь преобразовать вышеупомянутый алгоритм в чистый поток Java 8? 🙂

Рекомендации

• Википедия – простое число
• Таблица простых чисел и калькулятор

Алгоритм Java Java 8 Java 9 поток простых чисел