Быстрая проверка натурального числа на простоту

@Thinker · Регистрация: 26.08.2011

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

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

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}$ , то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм

C++
1
2
3
4
5
6
7
8
9
10
11
int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}

В данном алгоритме из множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ , которые взаимно просты с m. Например, если m = 6 = 2*3, то из этого множества отбрасывается 66% элементов (ненужных проверок). В этом случае алгоритм будет быстрее предыдущего при больших n

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Prime(unsigned long a)
{
   unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}

Если m = 30 = 2*3*5, то такой алгоритм будет еще быстрее и отбрасывает уже 74% лишних элементов

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Prime(unsigned long a)
{
   unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 || a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
      return 0;
   bound = sqrt((double)a);
   i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
   while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
   {
       i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
   }
   if (i8 <= bound ||
      i1 <= bound && a % i1 == 0 ||
      i2 <= bound && a % i2 == 0 ||
      i3 <= bound && a % i3 == 0 ||
      i4 <= bound && a % i4 == 0 ||
      i5 <= bound && a % i5 == 0 ||
      i6 <= bound && a % i6 == 0 ||
      i7 <= bound && a % i7 == 0)
         return 0;
   return 1;
}

Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.

@Jin X · 04.03.2019, 17:41

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

Создать упорядоченный массив всех простых чисел от 2 до 9973, а проверяемое число искать двоичным поиском в этом массиве... Проверяться будет "пулей" !

Во-первых, это слишком медленно.
Во-вторых, зачем использовать 1129*2 = 2258 байт памяти, когда можно 10000/8/2 = 625 ?

Для этого нужно создать битовый набор, в котором отмечать простые числа как 1, составные - как 0. Разумеется, только для нечётных чисел.

А вообще, по теме welcome сюда: https://www.cyberforum.ru/blog... g5712.html

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

Есть ещё такой вариант (наиболее быстрый из более или менее адекватных; на 25% быстрее выложенного в статье или того, что в шапке этого топика):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cmath>
#include <ctime>
 
using std::cout;
 
// Тест простоты числа n
bool is_prime(unsigned long n)
{
  // Проверяем, что число больше 1, а также частные случаи простых чисел (2, 3, 5, 7 и 11)
  if (n <= 12) {
    return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11);
  }
  // Проверяем делимость на 2, 3, 5, 7 и 11
  // p.s. При оптимизации нормальными компиляторами с опцией -O2 деление (взятие остатка от деления)
  // на константу будет выполняться быстрее, чем на переменную с заранее неизвестным значением
  if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0) { return false; }
 
  // Проверяем делимость на остальные числа, не делящиеся на 2, 3, 5, 7 и 11, начиная с 13
  // (с приращением, взятым из массива delta): 11, 13, 17, 19, 23, 29, 31, 37, 41, 43...
  static const unsigned char delta[480] = {
    4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4,
    14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6,
    2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6,
    2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4,
    12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2,
    4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4,
    2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4,
    2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8,
    4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2,
    10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2,
    4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2,
    4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4,
    8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2,
    10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2,
    6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6,
    2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4,
    8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
    10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2,
    4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4,
    2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12 };  // массив приращений
  for (unsigned long div = 13, idx = 0, max_div = sqrt(n);  // idx - индекс в массиве delta
    div <= max_div;
    div += delta[idx], idx = (idx == 479 ? 0 : idx + 1)) {  // увеличиваем индекс с остатком от деления на 480
    if (n % div == 0) { return false; }
  }
 
  // Число простое
  return true;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t _start_time;
public:
  // Запустить таймер
  void start()
  {
    _start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - _start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main()
{
  // Вывод простых чисел до 1'000 (тест Миллера)
  for (unsigned long n = 0; n < 1'000; ++n) {
    if (is_prime(n)) {
      cout << n << " ";
    }
  }
  cout << "\n\n";
 
  // Замер производительности
  TimeMeasure tm;
  tm.start();
  int count = 0;
  for (unsigned long n = 0; n <= 10'000'000; ++n) {
    if (is_prime(n)) { ++count; }
  }
  tm.stop_and_show();
  cout << "count = " << count << "\n";
 
  return 0;
}

Вариант проще

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cmath>
#include <ctime>
 
using std::cout;
 
// Тест простоты числа n
bool is_prime(unsigned long n)
{
  // Проверяем, что число больше 1, а также частные случаи простых чисел (2, 3, 5 и 7)
  if (n <= 10) {
    return (n == 2 || n == 3 || n == 5 || n == 7);
  }
  // Проверяем делимость на 2, 3, 5 и 7
  // p.s. При оптимизации нормальными компиляторами с опцией -O2 деление (взятие остатка от деления)
  // на константу будет выполняться быстрее, чем на переменную с заранее неизвестным значением
  if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) { return false; }
 
  // Проверяем делимость на остальные числа, не делящиеся на 2, 3, 5 и 7, начиная с 11
  // (с приращением, взятым из массива delta): 11, 13, 17, 19, 23, 29, 31, 37, 41, 43...
  static const unsigned char delta[48] = {
    2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2,
    4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10 };  // массив приращений
  for (unsigned long div = 11, idx = -1, max_div = sqrt(n);  // idx - индекс в массиве delta
    div <= max_div;
    div += delta[idx], idx = (idx == 47 ? 0 : idx + 1)) {  // увеличиваем индекс с остатком от деления на 48
    if (n % div == 0) { return false; }
  }
 
  // Число простое
  return true;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t _start_time;
public:
  // Запустить таймер
  void start()
  {
    _start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - _start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main()
{
  // Вывод простых чисел до 1'000 (тест Миллера)
  for (unsigned long n = 0; n < 1'000; ++n) {
    if (is_prime(n)) {
      cout << n << " ";
    }
  }
  cout << "\n\n";
 
  // Замер производительности
  TimeMeasure tm;
  tm.start();
  int count = 0;
  for (unsigned long n = 0; n <= 10'000'000; ++n) {
    if (is_prime(n)) { ++count; }
  }
  tm.stop_and_show();
  cout << "count = " << count << "\n";
 
  return 0;
}

Ещё проще (примерно как в шапке этого топика, скорость та же)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cmath>
#include <ctime>
 
using std::cout;
 
// Тест простоты числа n
bool is_prime(unsigned long n)
{
  // Проверяем, что число больше 1, а также частные случаи простых чисел (2, 3 и 5)
  if (n <= 5) {
    return (n >= 2 && n != 4);
  }
  // Проверяем делимость на 2, 3 и 5
  // p.s. При оптимизации нормальными компиляторами с опцией -O2 деление (взятие остатка от деления)
  // на константу будет выполняться быстрее, чем на переменную с заранее неизвестным значением
  if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0) { return false; }
 
  // Проверяем делимость на остальные числа, не делящиеся на 2, 3 и 5, начиная с 7
  // (с приращением, взятым из массива delta): 7, 11, 13, 17, 19, 23, 29, 31, 37...
  static const unsigned char delta[8] = { 4, 2, 4, 2, 4, 6, 2, 6 };  // массив приращений
  for (unsigned long div = 7, idx = 0, max_div = sqrt(n);  // idx - индекс в массиве delta
    div <= max_div;
    div += delta[idx], idx = idx+1 & 7) {  // увеличиваем индекс на 1 с остатком от деления на 8
    if (n % div == 0) { return false; }
  }
 
  // Число простое
  return true;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t _start_time;
public:
  // Запустить таймер
  void start()
  {
    _start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - _start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main()
{
  // Вывод простых чисел до 1'000 (тест Миллера)
  for (unsigned long n = 0; n < 1'000; ++n) {
    if (is_prime(n)) {
      cout << n << " ";
    }
  }
  cout << "\n\n";
 
  // Замер производительности
  TimeMeasure tm;
  tm.start();
  int count = 0;
  for (unsigned long n = 0; n <= 10'000'000; ++n) {
    if (is_prime(n)) { ++count; }
  }
  tm.stop_and_show();
  cout << "count = " << count << "\n";
 
  return 0;
}

Байт · 04.03.2019, 17:47

Сообщение от Jin X

когда можно 10000/8/2 =

Можно даже 10000/30

@Jin X · 04.03.2019, 17:49

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

Можно даже 10000/30

Можно, но геморно сопоставлять число индексу.
Хотя, может, и не слишком геморно, я пока даже не пытался этого делать...

@Catstail · 04.03.2019, 18:03

Сообщение от Jin X

Во-первых, это слишком медленно.
Во-вторых, зачем использовать 1129*2 = 2258 байт памяти, когда можно 10000/8/2 = 625 ?
Для этого нужно создать битовый набор, в котором отмечать простые числа как 1, составные - как 0. Разумеется, только для нечётных чисел.

- не думаю, что здесь так важна копеечная экономия памяти. А "слишком медленно" - по сравнению с чем?

@Jin X · 04.03.2019, 19:07

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

не думаю, что здесь так важна копеечная экономия памяти

Задумаетесь, когда кол-во чисел пойдёт на десятки и сотни миллионов

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

А "слишком медленно" - по сравнению с чем?

По сравнению с бинарным поиском.

@Catstail · 04.03.2019, 19:14

Сообщение от Jin X

Задумаетесь, когда кол-во чисел пойдёт на десятки и сотни миллионов

- так я-то писал (в 2012-м) о числах до 10 тыс...

Да, если использовать битовый массив, то будет быстрее двоичного поиска. Согласен. Правда Ваша.

@Jin X · 04.03.2019, 19:39

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

так я-то писал (в 2012-м) о числах до 10 тыс...

Да, я понял. Просто сейчас нужно 10 тыс, а завтра понадобится 10 млн. Зачем заново переписывать функцию, когда можно сразу сделать оптимально и на все случаи жизни, что называется?

Байт · 04.03.2019, 23:40

Сообщение от Jin X

Просто сейчас нужно 10 тыс, а завтра понадобится 10 млн

Все это копеечки, уважаемый. Реально задачу нахождения простых чисел интересуют штуки порядка 10^10¹⁰. Или больше. И тут даже есть возможность весьма приличную денежку заработать. А эти улучшения на 2 процента... Ну, как развлечения досужего ума, это все неплохо...

Добавлено через 30 минут
Jin X, вы лучше на решето Аткина посмотрите. Я, по правде, в нем так и не разобрался. Но говорят, оно дает выигрыш на порядок. И математика там симпатичная, не шибко заумная...

@Вадим Тукаев · 05.03.2019, 07:25

Если нужно проверять на простоту числа до 10000, то проще всего тупо их все во множество положить.

А учитывая объем памяти современных компьютеров, такой трюк и с 10000000 прокатит. Я недавно видел простенькое приложеньице, про которые в 90-х говорили "и эта фитюлька после компиляции в Дельфи 400 Кбайт весит??? Не, я лучше на С++ перепишу" весом... более 400 Мегабайт. И ее даже пытаются продавать за небольшую денежку. И ведь кто-то наверняка покупает...

@Jin X · 05.03.2019, 15:46

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

Jin X, вы лучше на решето Аткина посмотрите.

Это в планах.
Кстати, интересует вопрос. Что быстрее: решето Аткина или Эратосфена?

Добавлено через 1 минуту

Сообщение от Jin X

11, 13, 17, 19, 23, 29, 31, 37, 41, 43...

Опечатка, 11 тут не будет

И лучше всё же unsigned int, чем unsigned long (иначе на Linux 64 тормозить будет).

Байт · 05.03.2019, 19:42

Сообщение от Jin X

Что быстрее: решето Аткина или Эратосфена?

Народ говорит, что Аткин пошустрее будет

Сообщение от Jin X

лучше всё же unsigned int, чем unsigned long

Все блох ловите? Ну-ну...

@Jin X · 05.03.2019, 20:40

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

Все блох ловите? Ну-ну...

Уверены?
На Linux 64 long имеет размер 8 байт, а не 4, как на винде.
Уж не знаю, почему такая разница в скорости (раз система 64-битная), но к примеру, на tio.run разница в 2 раза: unsigned int и unsigned long

@alexu_007 · 28.05.2020, 22:35

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

Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.

Нехилый алгоритм, хоть и непонятный. Работает в 2.3 раза быстрее, чем простым делением.

Байт · 12.06.2020, 10:54

Вот такой код, решающий немного другую задачу. А именно, Найти K-е простое число. По ходу находятся все первые K простых чисел

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int>primes;
primes.reserve(K);  // Чтоб не было лишних перераспределений памяти...
for(i=2; primes.size() < K; i++) {
  bool isP = true;
  for(j=0; j< primes.size(); j++) {
    int p = primes[j];
    if (p*p > i) break;
    if (i%p) == 0) {
     isP = false;
     break;
   }
  }
   if (isP) primes.push_back(i);
}
cout << primes[primes.size() - 1);

Тут проверяется делимость только на простые, то есть выбрасываются из проверки не только 2, 3, 5, но и все простые вообще.
Конечно, для определения простоты конкретного числа, этот подход не быстр. Его модификации можно предложить, когда требуется определить простоту множества чисел. С расширением вектора primes и двоичным поиском.
Но вот эффективно применить его к анализу конкретного числа не получается...

@TheCalligrapher · 26.01.2024, 21:20

Понятно, что для проверки числа на простоту достаточно проверить его делимость только на простые делители, не превосходящие квадратного корня из числа. То есть хорошо иметь под руками готовую таблицу простых чисел. Однако, даже без таблицы простых чисел можно выполнить определенные оптимизации и заранее отсеять бесперспективные делители на основе известных свойств простых чисел. В частности, одна из известных оптимизации (в категорию которых попадает и пост ТС), является следующая последовательность улучшений:

0. Ищем делители среди всех чисел от 2 до корня из n
1. Обрабатываем делитель 2 отдельно, затем ищем делители от 3 с шагом (+2)
2. Обрабатываем делители { 2, 3 } отдельно, затем ищем делители от 5 с шагом (+2,+4)
3. Обрабатываем делители { 2, 3, 5 } отдельно, затем ищем делители от 7 с шагом (+4,+2,+4,+2,+4,+6,+2,+6)
4. Обрабатываем делители { 2, 3, 5, 7 } отдельно, затем ищем делители от 11 с шагом (+2,+4,+2,+4,+6,+2,+6,+4,+2,+4,+6,+6,+2, +6,+4,+2,+6,+4,+6,+8,+4,+2,+4,+2,+4,+8,+ 6,+4,+6,+2,+4,+6,+2,+6,+6,+4,+2,+4,+6,+2 ,+6,+4,+2,+4,+2,+10,+2,+10)
5. И т.д. пока не надоест...

(см. Получить все простые делители числа)

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

---

Но на самом деле существует намного более остроумный способ проверки числа на простоту: при помощи регулярных выражений. (Навеяно чуть менее чем полностью сегодняшним постом в паблике "Ёжик в матане" в VK)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <string>
#include <regex>
#include <iostream>
 
int main() 
{
  std::regex r("(11+)\\1+");
  
  for (unsigned n = 2; n < 100; ++n)
    if (!std::regex_match(std::string(n, '1'), r))
      std::cout << n << " "; 
      
  std::cout << std::endl;      
}

Вывод

Code
1
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

@alexu_007 · 26.01.2024, 22:02

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

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

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

@TheCalligrapher · 26.01.2024, 22:10

Не по теме:

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

Чё это решили старую тему реанимировать?

Во-первых, для решения стандартных задач нужно поддерживать одну тему, какой бы "старой" она ни была.
Во-вторых, эта тема прилинкована из списка "коллекции решенных задач", то есть по вопросу проверки на простоту - вот это она и есть.

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

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

Я думаю, не надо объяснять, что это не более чем шутка. В которой, как обычно, есть лишь для шутки.

@Royal_X · 26.01.2024, 22:15

Не по теме:

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

Чё это решили старую тему реанимировать?

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

@alexu_007 · 27.01.2024, 11:26

Протестил я три кода на быстродействие, мой простенький и следующие два:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
bool testPrime1(quint64 x)
{
    quint32 nn = sqrt(x)/6 + 2;
    quint32 k;
 
    if(x == 2 || x == 3) return true;
 
    if(!(x % 2)) return false;
    if(!(x % 3)) return false;
 
    for(quint32 i = 1; i < nn; i++)
    {
        k = i * 6;
        if(!(x % (k+1))) return false;
        if(!(x % (k-1))) return false;
    }
 
    return true;
}
 
 
bool testPrime2(quint64 a)
{
     quint64 i1, i2, i3, i4, i5, i6, i7, i8, bound;
 
     if (a == 0 || a == 1) return false;
 
     if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17
             || a == 19 || a == 23 || a == 29) return true;
 
     if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 ||
         a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
         return false;
 
     bound = sqrt((double)a);
 
     i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
 
     while(i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
     {
         i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
     }
 
     if( i8 <= bound ||
        (i1 <= bound && a % i1 == 0) ||
        (i2 <= bound && a % i2 == 0) ||
        (i3 <= bound && a % i3 == 0) ||
        (i4 <= bound && a % i4 == 0) ||
        (i5 <= bound && a % i5 == 0) ||
        (i6 <= bound && a % i6 == 0) ||
        (i7 <= bound && a % i7 == 0) )  return false;
 
     return true;
}
 
 
bool testPrime3(quint64 n)
{
  // Проверяем, что число больше 1, а также частные случаи простых чисел (2, 3, 5, 7 и 11)
  if (n <= 12) {
    return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11);
  }
  // Проверяем делимость на 2, 3, 5, 7 и 11
  // p.s. При оптимизации нормальными компиляторами с опцией -O2 деление (взятие остатка от деления)
  // на константу будет выполняться быстрее, чем на переменную с заранее неизвестным значением
  if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0) { return false; }
 
  // Проверяем делимость на остальные числа, не делящиеся на 2, 3, 5, 7 и 11, начиная с 13
  // (с приращением, взятым из массива delta): 11, 13, 17, 19, 23, 29, 31, 37, 41, 43...
  static const unsigned char delta[480] = {
    4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4,
    14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6,
    2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6,
    2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4,
    12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2,
    4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4,
    2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4,
    2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8,
    4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2,
    10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2,
    4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2,
    4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4,
    8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2,
    10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2,
    6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6,
    2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4,
    8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
    10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2,
    4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4,
    2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12 };  // массив приращений
 
  for (quint64 div = 13, idx = 0, max_div = sqrt(n);  // idx - индекс в массиве delta
    div <= max_div;
    div += delta[idx], idx = (idx == 479 ? 0 : idx + 1)) {  // увеличиваем индекс с остатком от деления на 480
    if (n % div == 0) { return false; }
  }
 
  // Число простое
  return true;
}

Результат на числе 18000000000000000133. Цифра 1 вначале - это возвращаемый функцией результат (число опознано как простое):

@TheCalligrapher · 27.01.2024, 11:29

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

Протестил я три кода на быстродействие, мой простенький и следующие два:

Вы уже приходили к практически тем же результатам и выводам: Получить все простые делители числа

Новые блоги и статьи Все статьи Все блоги /
Знаете, от чего появляется стресс? kumehtar 15.07.2026 Стресс появляется оттого, что вы, зная как поступить правильно, делаете наоборот. Ларри Уингет	Нас бьют, а мы крепчаем? Какая чушь! kumehtar 15.07.2026 Вот это вот бытующее мнение, что человек меняется только под действием проблем, всегда считал вредоносным. Поверь, от проблем у людей появляются не изменения, а нервное расстройство и ПТСР. А. . .	сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .
Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .	сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .

@Вадим Тукаев 312 / 293 / 116 Регистрация: 23.01.2018 Сообщений: 933
	05.03.2019, 07:25
	Если нужно проверять на простоту числа до 10000, то проще всего тупо их все во множество положить. А учитывая объем памяти современных компьютеров, такой трюк и с 10000000 прокатит. Я недавно видел простенькое приложеньице, про которые в 90-х говорили "и эта фитюлька после компиляции в Дельфи 400 Кбайт весит??? Не, я лучше на С++ перепишу" весом... более 400 Мегабайт. И ее даже пытаются продавать за небольшую денежку. И ведь кто-то наверняка покупает... 0