поиск простых чисел php

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

Поиск простых чисел разными способами. Сравнение алгоритмов поиска простых чисел по памяти и времени.

Подготовка

Записать php 7 в папку c:\php, поместить в эту же папку файл php7.bat со следующим содержимым. Создать папку c:\php\localhost, в неё положить php файлы.

Поиск простых чисел

Перебор простых делителей

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

Перебор простых делителей +=2 и 235

Решето Эратосфена

Решето Аткина

Решето Сундарама

Решето Сундарама простое, оно пусть будет домашним заданием.

Результаты

Для сравнения: WinRAR/Меню/Операции/Тест быстродействия, без многопоточности =1200.

Литература

О песочнице

Это «Песочница» — раздел, в который попадают дебютные посты пользователей, желающих стать полноправными участниками сообщества.

Если у вас есть приглашение, отправьте его автору понравившейся публикации — тогда её смогут прочитать и обсудить все остальные пользователи Хабра.

Чтобы исключить предвзятость при оценке, все публикации анонимны, псевдонимы показываются случайным образом.

О модерации

Не надо пропускать:

Источник

Поиск простых чисел на PHP

Простые числа — это натуральные числа больше 1, которые делятся только сами на себя или на 1. Часто возникающая (например, при шифровании данных) задача — найти все простые числа от 2 до заданного N. Для этого придумано несколько алгоритмов разной эффективности. Давайте рассмотрим их реализацию на PHP.

Простой перебор делителей

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

Суть алгоритма: мы просто последовательно перебираем все числа от 2 до N и проверяем, простые они, или нет. Функция проверки на простоту перебирает все нечетные числа от 2 до квадратного корня из N и, если находит такое, на которое N делится без остатка, то число считается составным, а если не находит, то простым.

Эффективность такого алгоритма: O(n * sqrt(n))

Решето Эратосфена

Этот алгоритм как бы «просеивает» все числа от 0 до максимального N через условное решето несколько раз. Сначала последовательно исключаются все числа, кратные 2. Само число добавляется в массив простых чисел. Далее из оставшихся исключаются все числа, кратные следующему простому числу — трем. 4 уже было удалено из исходного массива, соответственно, следом удаляются все числа, кратные 5, и так далее, пока не будут перебраны все числа.

Вот пример решета Эратосфена на PHP:

Метод нахождения псевдопростых чисел с использованием теста простоты Ферма

Данный метод позволяет находить простые числа гораздо быстрее предыдущих двух, однако, это будут псевдопростые числа, то есть числа, которые являются простыми лишь с некоторой (тем не менее, очень высокой, около 100%) вероятностью.

Здесь используется тест Ферма, который гласит: если p-простое число, то если возвести число n в степень (p-1), а потом взять результат возведения в степень по модулю p (остаток от деления на p), то в итоге получится 1.

Вот реализация поиска простых чисел с использованием теста Ферма на PHP:

Эффективность такого алгоритма O(n * log 2 n * log (log n) * log (log (log n)))

Кроме указанных алгоритмов существуют и такие, как:

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

Источник

Поиск простых чисел в массиве

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Поиск простых чисел
Привет всем,задача заключается в том что бы вывести из массива опр. количество простых.

Поиск простых чисел в массиве
Здесь, на форуме для начинающих, была задачка, в которой в матрице A(m,n), состоящей из целых.

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

Поиск простых чисел в массиве (TASM)
Здравствуйте. помоги пожалуйста. нужно написать программу на ассемблере (тасм) поиска простых чисел.

Спасибо не знаю дошло ли сообщение(в отправленных нет) но не мог бы ты или еще кто-нибудь объяснить\откомментировать строки а то хочется понять как это работает!)

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Поиск простых чисел в одномерном массиве
Доброго времени суток! Нужно найти все простые числа в одномерном массиве. Для решения моей.

Найти количество простых чисел в массиве из 10 положительных целых чисел
Задание: Описать функцию IsPrime(K) логического типа, возвращающую true, если целый параметр К.

Нахождение простых чисел в массиве
Ввести 20 чесел в массив и найти среди них все простые числа Пожалйста помогите 🙁 Буду оч.

Источник

Использовав 2 недавних темы с этого сайта, сделал для себя штуку, о которой мечтал:

Есть ли способ сделать аналогичные вычисления и запись их в таблицу быстрее? Ну как-нибудь с большим сжиранием памяти )

5 ответов 5

79 тыс. записей. Форма очень мешает, нужно ее чем то заменить, в общем, что б без кнопки было.

Господа, прошу заценить креатив. Работает быстрее всех ваших примеров. Но не идеально.

В этом файле: алгоритм Решето Эратосфена до 210, перебор на множители половины от максимума. Думаю вот от него и нужно думать, как быстрее дальше. Нужно как-то записать все значения таблицы в массив, и перебирать на множители уже из массива, тогда будет в СОТНИ раз быстрее.

Если я вас правильно понял, то вы хотите найти все простые числа например из 200 000. Попробуйте реализовать алгоритм Решето Эратосфена. Скажу сразу сам не пробовал реализовать, но читал что достаточно шустро работает, правда все его реализации видел на C.

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

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

Обновлено

Предложу свое решение, оно базируется на «решете Эратосфена» и в нем отсутствует деление. Есть только поиск по элементам массива. Алгоритм таков:

Перебираем все числа, начиная с 2.

для решения: создаем таблицу в MySQL:

Создаем хранимую процедуру в MySQL:

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

Вызываем процедуру для каждого числа (просто по очереди скармливаем все числа процедуре).

Получаем по одному обращению к базе из php на число (т.е. собственно вызов процедуры).

Для увеличения быстродействия можно:

Быстродействие не проверял.

Программа написана на PHP и содержит следующие функции:

Источник

Массив простых чисел от определенного промежутка

Получается, я сначала объявляю переменные, потом функцию. А далее в функции как расписать, чтобы этот массив вывести?

Помощь в написании контрольных, курсовых и дипломных работ здесь.

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

Понял. Получается, что рекурсию в этой задаче использовать неуместно?

Но в данном случае неуместно. Рекурсия тяжелее в понимании + плюс может быть очень ресурсозатратной (каждая итерация увеличивает стек вызовов).

Кстати, по ТЗ требовалось получить массив простых чисел, странно что никто не заметил
Гугл выдает весьма нетривиальные алгоритмы, есть где разгуляться

Добавлено через 48 секунд
Хех, пока писал, вы уже опередили)

tarasalk, вообще я хочу сказать, что PHP довольно быстрый язык среди интерпретируемых, зря на него «бочку катят» (или катили). Тестировал приблизительную скорость наполнения массива 500 000 элементами, скрипт отрабатывает за семь-восемь десятых секунды. И это на половине миллиона итераций! В то время, как на языке IS-Builder 500 итераций в цикле уже много! У меня недавно была ситуация, когда 333 итерации выполнялись 18-20 секунд. Конечно, справедливости ради, нужно учитывать, что в том цикле было взаимодействие со sql-сервером, но даже если аналогичный скрипт запустить на PHP, он при той же логике отработает максимум за две секунды.

Всем спасибо) Всё сделал через решето Эратосфена. Ну и чуть поредачил код.
http://langtoday.com/?p=590

Добавлено через 1 час 4 минуты
Так. Теперь возникла еще одна проблема. Вот к примеру код этой задачки

Как в этот массив, который получился на выходе, для каждой тройки чисел добавить дополнительный ключ s, содержащий результат расчета площади трапеции со сторонами a и b, и высотой c. Тут уже посложнее задачка идет, с ней я боюсь не справлюсь)

Добавлено через 13 минут
Забыл написать. Тут сверху код вставил, а саму задачку, из которой этот массив получаем, не кинул.

я знаю, что тут проверки нет кратности 3, я это доработаю.

Источник