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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

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