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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

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