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

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

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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

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

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

@alexu_007 736 / 700 / 110 Регистрация: 29.05.2015 Сообщений: 4,279
	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

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

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

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

Решение