Функция проверки числа на простоту

@Patrik1001 · Регистрация: 28.01.2020

Author24 — интернет-сервис помощи студентам

10. **Написать функцию, которая возвращает истину, если переданное число простое, и ложь, если не простое.
Простое число – это число, которое делиться ТОЛЬКО на 1 и на себя (2, 5, 7, 11, 13, 17, 19, 23, 29 и т.д.).

Байт · 11.02.2020, 16:12

Patrik1001, В низ страницы не заглядывал?

C++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
bool IsPime(int n)
{
   for(int i=2; i*i <= n; i++)
     if (n%i==0) return false;
   return true;
}

@alexu_007 · 11.02.2020, 16:37

Можно чуток ускорить - нет необходимости делить на чётные числа. До цикла проверяем на 2. В цикле на 3, 5, 7 и т.д.

Байт · 11.02.2020, 16:50

Сообщение от alexu_007

Можно чуток ускорить

Можно рассматривать числа 6n+-1 или даже 30n +-1 +-7 +- 11 +-13. Небольшое ускорение это даст. В разы. Но разы - это не повод. Вот ежли бы порядки...

@valen10 · 11.02.2020, 16:56

alexu_007, в рамках поставленной задачи не имеет смысла, ИМХО. Останутся числа, кратные 3, 5, 7 и т.д., делить на которые тоже нет необходимости. Только код усложнится.

А вот если взять таблицу простых чисел, то будет уже что-то

Байт · 11.02.2020, 17:07

Сообщение от valen10

А вот если взять таблицу простых чисел, то будет уже что-то

Тут дело такое. Если нужно определить простоту одного какого-то числа, то не стоит и огород городить. А вот если требуется находить простоту многих чисел, тогда да, таблица делу поможет. Хотя для больших чисел имеет смысл и для одного...
В общем, дилемма простая, как весь наш мир "Скорость - Память"

@andrey_f · 11.02.2020, 21:06

C++    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cmath>
bool isPrime(int num) {
  if(num > 0){
    if(num == 1){
      return false;
    }
  for(int x = 2; x <= sqrt(num); ++x){
    if(num%x == 0 && x != num){
      return false;
    }
  }
  return true;
  }else{
    return false;
  }
}

Байт · 11.02.2020, 21:19

Сообщение от andreyfreelans

for(int x = 2; x <= sqrt(num); ++x){

Каждый раз вычислять sqrt при проверки окончания цикла? Побойтесь Бога!
Тогда уж так

C++    
        
    Скопировано
1
2
double s = sqrt(num);
for(int x = 2; x <= s; ++x){

Но это вообще плохая практика, привлекать для целочисленных задач типы, выходящие за их пределы....

@valen10 · 11.02.2020, 22:52

Сообщение от Байт

А вот если требуется находить простоту многих чисел, тогда да, таблица делу поможет. Хотя для больших чисел имеет смысл и для одного...

Вот интересно стало, есть ли какое-то практическое применение у способа с перебором делителей, чтобы заниматься его оптимизацией. Студенту сдать лабу и так сойдет. Для больших чисел существуют более специфичные алгоритмы. А нужно ли где-то на практике проверять простоту не очень больших чисел?

@rikimaru2013 · 11.02.2020, 22:57

Байт, разве компиляторы в 2020 не умеют кэшировать значение?

@valen10 · 11.02.2020, 23:17

Не по теме:

Сообщение от rikimaru2013

разве компиляторы в 2020 не умеют кэшировать значение?

В 2020 компиляторы умеют не только кэшировать значения, но и так тоже:

In C++14 you just write «auto auto(auto auto) { auto; }». The compiler infers the rest from context.

Источник xD

@alexu_007 · 12.02.2020, 08:13

Сообщение от valen10

alexu_007, в рамках поставленной задачи не имеет смысла, ИМХО. Останутся числа, кратные 3, 5, 7 и т.д., делить на которые тоже нет необходимости. Только код усложнится.
А вот если взять таблицу простых чисел, то будет уже что-то

C    
        
    Скопировано
1
2
3
for(int i = 2; i <= sqrt(n); i++)
 
for(int i = 3; i <= sqrt(n); i+=2)

Где тут усложнение? А цикл сокращается ровно в 2 раза.

@valen10 · 12.02.2020, 17:23

Сообщение от alexu_007

Где тут усложнение?

if (n % 2 == 0) ... перед циклом.

Но вопрос немного в другом. Цель такой оптимизации? Ради оптимизации. Сложность как была $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt n)$ , так и осталась. Если будем проверять маленькие числа, то разница в 2 раза мало влияет на результат, а если большие - не спасет.

Согласен с Вами, оптимизировать можно. Но почему именно в 2 раза? Если пойти и дальше, избавимся от 9, 27, ..., $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^k$ . Затем от степеней 5, 7 и т.д. Не ясно только, когда остановиться. Если продолжить, то придем к описанию таблицы простых чисел. Если сделаем только 2-3 шага, то никуда не уйдем от $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt n)$ .

@alexu_007 · 12.02.2020, 20:16

Сообщение от valen10

if (n % 2 == 0) ... перед циклом.

Вы это серьёзно? n%2 выполняется один раз, а цикл уменьшается вдвое.

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

Цель такой оптимизации? Ради оптимизации. Сложность как была , так и осталась. Если будем проверять маленькие числа, то разница в 2 раза мало влияет на результат, а если большие - не спасет.

По-любому, ускорение алгоритма почти в 2 раза без каких-либо усилий (только силой интеллекта) есть очень хорошо. Даже если и не нада.

Байт · 12.02.2020, 21:42

Не по теме:

alexu_007, вашу бы энергию и убежденность в очевидных вещах - как бы в мирное русло направить?

valen10, вот такая схема вырисовывается. По дороге делений выясняем простоту очередных делителей. И в случае удачи - добавляем их в массив простых. Не знаю, не понимаю пока, даст ли это хоть какой эффект при выяснении для одного числа. Для кучи - даст несомненно. Насколько? Если в разы - это неинтересно. Если на порядок - тогда имеет смысл.

@alexu_007 · 13.02.2020, 06:46

Сообщение от Байт

Насколько? Если в разы - это неинтересно.

Индусский код - работает и ладно? Если бы все старались писать так, что-бы работало в целых! 2 раза быстрее - тогда и игры бы не тормозили, и страницы быстрее грузились.

@valen10 · 19.02.2020, 22:52

Сообщение от Байт

По дороге делений выясняем простоту очередных делителей

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

Сообщение от Байт

Насколько? Если в разы - это неинтересно. Если на порядок - тогда имеет смысл.

Я правильно понял, что в результате этих действий у нас начнет формироваться таблица простых чисел? Если да, то можно, наверное, теорему о распределении простых чисел применить.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{{\pi (n)} \over {n / \ln n}} \rightarrow 1$ при $https://www.cyberforum.ru/cgi-bin/latex.cgi?n \rightarrow \infty$ .

Допустим, мы построили уже таблицу простых чисел от 2 до k. Тогда числа, входящие в интервал $https://www.cyberforum.ru/cgi-bin/latex.cgi?[2; k]$ проверим за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O({\ln m})$ , где m - размер таблицы (бинарный поиск), входящие в интервал $https://www.cyberforum.ru/cgi-bin/latex.cgi?[k + 1; k^2]$ - за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O({{n} \over {\ln n}})$ , а дальше - перебор делителей, который благодаря таблице конечно сократится (полагаю, что в разы).

Не по теме:

Математик из меня не очень. Байт, и почему мне кажется, что Вы знаете решение :D
p.s. прошу прощения за столь поздний ответ.

Байт · 19.02.2020, 23:14

Сообщение от valen10

почему мне кажется, что Вы знаете решение

не-а.. Не знаю. Просто пришло в голову, что можно попытаться совместить эти 2 подхода - перебор и решето. Но, имхо, какого-то революционного прорыва это не даст.
Простые числа - задача древняя. Более того - реально востребованная в "промышленности". За нахождение хорошего простого числа можно и слегка пополнить свой тощий кошелек.

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

@alexu_007 · 20.02.2020, 09:43

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

Новые блоги и статьи Все статьи Все блоги /
Анализ и линтинг кода JavaScript: ESLint, Prettier и JSHint run.dev 26.04.2025 JavaScript прошёл долгий путь от простого языка для анимации веб-страниц до основы современной веб-разработки. С ростом сложности приложений, увеличением кодовых баз и масштабированием команд. . .	Паттерны в Python: Singleton, Factory и Observer py-thonny 26.04.2025 Паттерны проектирования — это проверенные временем решения типовых проблем разработки программного обеспечения. Их история берёт начало с книги "Приёмы объектно-ориентированного проектирования. . . .	Исключения в C#: Stack Overflow, Access Violation и Out of memory stackOverflow 26.04.2025 Исключения в C# — это не только механизм оповещения о проблемах, а целое искусство управления потоком выполнения программы в экстремальных ситуациях. Обычное исключение, например,. . .	Логирование в C# ASP.NET Core с помощью Serilog, ElasticSearch, Kibana stackOverflow 25.04.2025 Помните те времена, когда для анализа проблемы приходилось подключаться к серверу, искать нужный лог-файл среди десятков других и вручную фильтровать тысячи строк в поисках ошибки? К счастью, эти дни. . .	Структура "железный OnKeyUp" вместо антидребезга. Полностью асинхронный счётчик. Hrethgir 25.04.2025 Программа для симуляции схемы - Logisim Evolution В общем какое-то время отвлёкся, так было надо, теперь когда запилю это на verilog и FPGA , досоставлю заявку в ФИПС на полезную модель - не готов. . .
Автоматизация Amazon Web Services (AWS) с Boto3 в Python py-thonny 25.04.2025 Облачные вычисления стали неотъемлемой частью современной ИТ-инфраструктуры, а Amazon Web Services (AWS) занимает лидирующие позиции среди провайдеров облачных услуг. Управление многочисленными. . .	Apache Kafka vs RabbitMQ в микросервисной архитектуре ArchitectMsa 25.04.2025 Современная разработка ПО всё чаще склоняется к микросервисной архитектуре — подходу, при котором приложение разбивается на множество небольших, автономных сервисов. В этой распределённой среде. . .	Параллельное программирование с OpenMP в C++ NullReferenced 24.04.2025 Параллельное программирование — подход к созданию программ, когда одна задача разбивается на несколько подзадач, которые могут выполняться одновременно. Оно стало необходимым навыком для. . .	Цепочки методов в C# с Fluent API UnmanagedCoder 24.04.2025 Современное программирование — это не только решение функциональных задач, но и создание кода, который удобно поддерживать, расширять и читать. Цепочки методов и Fluent-синтаксис в C# стали мощным. . .	Мульти-тенантные БД с PostgreSQL Row Security Codd 23.04.2025 Современные облачные сервисы и бизнес-приложения всё чаще обслуживают множество клиентов в рамках единой программной инфраструктуры. Эта архитектурная модель, известная как мульти-тенантность, стала. . .

@Patrik1001 0 / 0 / 0 Регистрация: 28.01.2020 Сообщений: 28

	Функция проверки числа на простоту 11.02.2020, 13:22. Показов 17501. Ответов 18 Метки нет (Все метки) 10. **Написать функцию, которая возвращает истину, если переданное число простое, и ложь, если не простое. Простое число – это число, которое делиться ТОЛЬКО на 1 и на себя (2, 5, 7, 11, 13, 17, 19, 23, 29 и т.д.). 0

@alexu_007 732 / 693 / 110 Регистрация: 29.05.2015 Сообщений: 4,187
	11.02.2020, 16:37
	Можно чуток ускорить - нет необходимости делить на чётные числа. До цикла проверяем на 2. В цикле на 3, 5, 7 и т.д. 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	11.02.2020, 16:56
	alexu_007, в рамках поставленной задачи не имеет смысла, ИМХО. Останутся числа, кратные 3, 5, 7 и т.д., делить на которые тоже нет необходимости. Только код усложнится. А вот если взять таблицу простых чисел, то будет уже что-то 1

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	11.02.2020, 22:57
	Байт, разве компиляторы в 2020 не умеют кэшировать значение? 0

Байт Диссидент 27710 / 17328 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	12.02.2020, 21:42
	Не по теме: alexu_007, вашу бы энергию и убежденность в очевидных вещах - как бы в мирное русло направить? valen10, вот такая схема вырисовывается. По дороге делений выясняем простоту очередных делителей. И в случае удачи - добавляем их в массив простых. Не знаю, не понимаю пока, даст ли это хоть какой эффект при выяснении для одного числа. Для кучи - даст несомненно. Насколько? Если в разы - это неинтересно. Если на порядок - тогда имеет смысл. 0

@alexu_007 732 / 693 / 110 Регистрация: 29.05.2015 Сообщений: 4,187
	20.02.2020, 09:43
	Программа, демонстрирующая работу 2-х алгоритмов решета эрастофена - простого и только с четными числами. Считает количество простых в заданном диапазоне, их сумму и время работы алгоритма. К сожалению, простой эрастофен крашится при диапазоне более 2,1 млрд, при 4,2 удалось проверить только вторым: Миниатюры 0

Функция проверки числа на простоту

Решение