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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;	FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .
[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .

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