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

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

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

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

Байт · 11.02.2020, 16:12

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

C++

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

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

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

@andreyfreelans · 11.02.2020, 21:06

C++

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

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

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

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

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

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

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

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

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

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

@valen10
	11.02.2020, 23:17 #11
	Не по теме: Сообщение от 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	13
	Сообщение от 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 716 / 676 / 110 Регистрация: 29.05.2015 Сообщений: 4,085
	12.02.2020, 20:16	14
	Сообщение от valen10 if (n % 2 == 0) ... перед циклом. Вы это серьёзно? n%2 выполняется один раз, а цикл уменьшается вдвое. Найти простые числа (например решетом Эрастофена) и делить на них - это имеет смысл, если нужно много чисел проверять на простоту. Тогда один раз отработает решето и много раз поиск простых. На одном числе ускорения не даст. Цель такой оптимизации? Ради оптимизации. Сложность как была , так и осталась. Если будем проверять маленькие числа, то разница в 2 раза мало влияет на результат, а если большие - не спасет. По-любому, ускорение алгоритма почти в 2 раза без каких-либо усилий (только силой интеллекта) есть очень хорошо. Даже если и не нада. 0

@alexu_007 716 / 676 / 110 Регистрация: 29.05.2015 Сообщений: 4,085
	13.02.2020, 06:46	16
	Сообщение от Байт Насколько? Если в разы - это неинтересно. Индусский код - работает и ладно? Если бы все старались писать так, что-бы работало в целых! 2 раза быстрее - тогда и игры бы не тормозили, и страницы быстрее грузились. 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	19.02.2020, 22:52	17
	Сообщение от Байт По дороге делений выясняем простоту очередных делителей Вот тут не совсем понял, как можно эффективно это сделать. Если каждый новый делитель проверять на простоту тем же алгоритмом, то картина складывается не очень хорошая (могу заблуждаться, не проверял, честно). Сообщение от Байт Насколько? Если в разы - это неинтересно. Если на порядок - тогда имеет смысл. Я правильно понял, что в результате этих действий у нас начнет формироваться таблица простых чисел? Если да, то можно, наверное, теорему о распределении простых чисел применить. $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

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

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

Решение