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

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

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

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

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

Начнем с основного определения. A prime number is a natural number greater than one that has no positive divisors other than one and itself.с

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

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

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

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

public static List primeNumbersBruteForce(int n) < ListprimeNumbers = new LinkedList<>(); for (int i = 2; 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 доnumber-1.

If at any point we encounter a number that is divisible, we return false. В конце, когда мы обнаруживаем, что это число не делится ни на одно из его предшествующих чисел, мы возвращаем истину, указывая, что это простое число.

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

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

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

Если число не является простым, это число можно разложить на два фактора, а именноa иb, т.е. number = а * Ь. If both a and b were greater than the square root of n, a*b would be greater than n.

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

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

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

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

public static List primeNumbersBruteForce(int n) < ListprimeNumbers = new LinkedList<>(); if (n >= 2) < primeNumbers.add(2); >for (int i = 3; 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))) .filter(n ->(n & 0X1) != 0) .allMatch(n -> x % n != 0); >

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

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

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

1. Создайте список последовательных целых чисел от 2 доn: (2, 3, 4,…, n)
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 > > List primeNumbers = new LinkedList<>(); for (int i = 2; 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.

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

Источник

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

Простое число – это число, которое делится нацело без остатка только на 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 которая принимает целое число, выводит на экран все простые числа от нуля до принятого числа. Используя только простые операции if и for Я составил, но что-то не помогает import java.util.Scanner;

public class prostue_chisla < public static void main(String[] args) < System.out.println("Введите положительное число: "); Scanner in = new Scanner(System.in); int input = in.nextInt(); boolean b = true; for (int P = 1; P System.out.println(P);> > > > 

7 ответов 7

Если используете java 8+ , лучше юзать в вашем случае IntStream для целых чисел:

public static boolean isPrime(final int number) < return IntStream.rangeClosed(2, number / 2).anyMatch(i ->number % i == 0); > 

System.out.println(isPrime(1)); // false System.out.println(isPrime(2)); // true 

public static void main(String[] args) < Scanner scanner = new Scanner(System.in); int top = scanner.nextInt(); for (int i=2;i> public static boolean checkSimple(int i) < if (i<=1) return false; else if (i <=3) return true; else if (i%2==0 || i %3 ==0) return false; int n = 5; while (n*n <=i)< if (i % n ==0 || i % (n+2) == 0) return false; n=n+6; >return true; > 

Алгоритм проверки на то, что число является простым взял отсюда : https://en.wikipedia.org/wiki/Primality_test

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

public static void main(String[] args) < System.out.println("Введите положительное число: "); Scanner in = new Scanner(System.in); int input = in.nextInt(); boolean b = true; for (int P = 2; P > if (b) System.out.println(P); else b = true; > > 

//variable 'input' is input numeric for (int i = 2; i > if (rez != null) < System.out.println(rez); >> 

Программа проверяет, числа от 11 и до бесконечности, и выводит количество простых чисел на экран + все простые числа + время работы программы. При желании можно отключить массив и выводить только количество простых чисел, что ускорит время работы программы процентов на 30. Без проблем можно запилить еще один метод, для проверки и вывода чисел до 10 и при помощи if проверять n

public class reshenie < public static void main(String[] args) < int count = 4;//начинаем с 4, т.к. до 10 нам известны все простые числа и программа их не обрабатывает. int n = 100000;//число до которого необходимо найти все простые числа ArrayListnumbers = new ArrayList<>();//создаем массив, необходим для вывода чисел на экран, можно и без массива, просто выводить каждое найденное простое число numbers.add(2);//добавляем в массив простые числа до 10(см count = 4) numbers.add(3); numbers.add(5); numbers.add(7); Date startTime = new Date();//время старта for (int i = 11; i  > Date finishTime = new Date();//время окончания работы алгоритма long ct = finishTime.getTime() - startTime.getTime();//время работы System.out.println("Время вычислений: " + ct + "ms");//вывод на экран времени работы System.out.println("Количество простых чисел: " + count);//вывод количества System.out.print(numbers);//вывод всех чисел > static boolean simple(int a) else < for (int j = 3; j  > > if (p > 0) else return true; > > 

Источник