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

@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 удалось проверить только вторым:

Новые блоги и статьи Все статьи Все блоги /
Списки и кортежи в Python: различия, особенности, применение py-thonny 13.04.2025 Python славится своей гибкостью при работе с данными. В арсенале языка есть две основные последовательные структуры данных, которые программисты используют ежедневно — списки и кортежи. Эти структуры. . .	Middleware в ASP.NET Core UnmanagedCoder 13.04.2025 В ASP. NET Core термин "middleware" занимает особое место. Что же это такое? Middleware представляет собой программные компоненты, которые формируют конвейер обработки HTTP-запросов в приложении. . . .	Таблицы лута в Unity с MinMaxCurve и AnimationCurve GameUnited 12.04.2025 Создание сбалансированного лута в играх — задача не из простых. Разработчики постоянно ищут способы настройки систем выпадения предметов, которые будут одновременно справедливыми для игроков и. . .	std::expected в C++: Управление ошибками bytestream 12.04.2025 Обработка ошибок всегда была важной и одновременно сложной задачей в программировании на C++. На протяжении долгого времени разработчики использовали различные подходы: возвращаемые коды ошибок,. . .	Nullable типы и операторы объединения null в C# UnmanagedCoder 12.04.2025 Многие шутят, что null — это миллиардная ошибка в программировании. И в этой шутке только доля шутки. Тони Хоар, создатель null-ссылки, сам назвал её своей "ошибкой на миллиард долларов". Почему?. . .
Аутентификация и авторизация JWT в микросервисах с API Gateway stackOverflow 12.04.2025 В традиционных монолитных приложениях безопасность часто реализуется как единый защитный периметр - пользователь проходит аутентификацию один раз, после чего получает доступ ко всем функциям системы. . . .	TypeScript: Интерфейсы vs Типы run.dev 12.04.2025 Современная разработка на JavaScript сталкивается с множеством проблем при масштабировании проектов. Типизация кода стала хорошим инструментом, помогающим избежать ошибок во время выполнения,. . .	Управление топиками и разделами Kafka Javaican 12.04.2025 Apache Kafka — распределенная платформа потоковой передачи данных, которая стала стандартом для построения высоконагруженных систем обмена сообщениями. В современной архитектуре микросервисов,. . .	Миграция монолита в Event-Driven микросервисную архитектуру на C# stackOverflow 11.04.2025 Монолитная архитектура – классический подход к разработке программного обеспечения. Это приложение, построенное как единое целое, где все компоненты тесно связаны между собой. Большинство проектов. . .	Go в Kubernetes: Управление ресурсами golander 11.04.2025 Разработчики Go-приложений в Kubernetes часто сталкиваются с неожиданными проблемами производительности и даже внезапными отказами контейнеров. Причина этого кроется в особенностях взаимодействия. . .

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

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

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

Байт Диссидент 27710 / 17328 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	11.02.2020, 16:50
	Сообщение от alexu_007 Можно чуток ускорить Можно рассматривать числа 6n+-1 или даже 30n +-1 +-7 +- 11 +-13. Небольшое ускорение это даст. В разы. Но разы - это не повод. Вот ежли бы порядки... 1

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

Байт Диссидент 27710 / 17328 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	11.02.2020, 17:07
	Сообщение от valen10 А вот если взять таблицу простых чисел, то будет уже что-то Тут дело такое. Если нужно определить простоту одного какого-то числа, то не стоит и огород городить. А вот если требуется находить простоту многих чисел, тогда да, таблица делу поможет. Хотя для больших чисел имеет смысл и для одного... В общем, дилемма простая, как весь наш мир "Скорость - Память" 1

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	11.02.2020, 22:52
	Сообщение от Байт А вот если требуется находить простоту многих чисел, тогда да, таблица делу поможет. Хотя для больших чисел имеет смысл и для одного... Вот интересно стало, есть ли какое-то практическое применение у способа с перебором делителей, чтобы заниматься его оптимизацией. Студенту сдать лабу и так сойдет. Для больших чисел существуют более специфичные алгоритмы. А нужно ли где-то на практике проверять простоту не очень больших чисел? 1

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

@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 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	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)$ . 1

@alexu_007 732 / 693 / 110 Регистрация: 29.05.2015 Сообщений: 4,184
	12.02.2020, 20:16
	Сообщение от valen10 if (n % 2 == 0) ... перед циклом. Вы это серьёзно? n%2 выполняется один раз, а цикл уменьшается вдвое. Найти простые числа (например решетом Эрастофена) и делить на них - это имеет смысл, если нужно много чисел проверять на простоту. Тогда один раз отработает решето и много раз поиск простых. На одном числе ускорения не даст. Цель такой оптимизации? Ради оптимизации. Сложность как была , так и осталась. Если будем проверять маленькие числа, то разница в 2 раза мало влияет на результат, а если большие - не спасет. По-любому, ускорение алгоритма почти в 2 раза без каких-либо усилий (только силой интеллекта) есть очень хорошо. Даже если и не нада. 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,184
	13.02.2020, 06:46
	Сообщение от Байт Насколько? Если в разы - это неинтересно. Индусский код - работает и ладно? Если бы все старались писать так, что-бы работало в целых! 2 раза быстрее - тогда и игры бы не тормозили, и страницы быстрее грузились. 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	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. прошу прощения за столь поздний ответ. 0

Байт Диссидент 27710 / 17328 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	19.02.2020, 23:14
	Сообщение от valen10 почему мне кажется, что Вы знаете решение не-а.. Не знаю. Просто пришло в голову, что можно попытаться совместить эти 2 подхода - перебор и решето. Но, имхо, какого-то революционного прорыва это не даст. Простые числа - задача древняя. Более того - реально востребованная в "промышленности". За нахождение хорошего простого числа можно и слегка пополнить свой тощий кошелек. Так что довольно глупо рассчитывать, что мы с вами откроем тут нечто замечательное. Так, развлечение и размятие шеи, на которой висит голова.... 0

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

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

Решение