Программа вывода простых чисел java

Вопрос по Шилдту. Java 8 руководство для начинающих.

Задача 10 во второй главе. Напишите программу, которая находила бы простые числа в пределах от 2 до 100. Код таков:

// Нахождение простых чисел в пределах от 2 до 100 class Prime  public static void main(String args[])  int i, j; boolean isprime; for(i=2; i  100; i++)  isprime = true; // проверить, делится ли число без остатка for (j=2; j  i/j; j++) // если число делится без остатка, значит, оно не простое if((i%j) == 0) isprime = false; if (isprime) System.out.println(i + " - простое число."); > > >

Источник

Алгоритм поиска простых чисел

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

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

public List getFirstPrimes( int count) List 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 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 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

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

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

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

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

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

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

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

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

 public static ListInteger> primeNumbersBruteForce(int n)    ListInteger> 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 ListInteger> primeNumbersBruteForce(int n)    ListInteger> 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 ListInteger> 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 ListInteger> 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;   >   >   >   ListInteger> 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 .

Источник