Непростые числа

Составное натуральное число n называется непростым (или не упрощаемым - unprimeable, не знаю, как правильно по-русски), если его нельзя превратить в простое, изменив одну любую цифру на любую другую.

Минимальное такое число в десятичной системе счисления - это груз 200. Unprimeable numbers образуют последовательность A118118 в oeis.org, только там их показано маловато.

Попробуем найти все такие числа в пределах до 10 миллионов (можно и больше), применив решетоподобный алгоритм. Далее приведён код на С++, проверенный в консоли актуальной сборки Visual Studio 2019 и прикреплён файл с числами, которых в наших границах поиска оказалось 2855168.

#include <iostream>
#include <fstream>
#include <cstdint>
#include <algorithm>
#include <vector>
using namespace std;

typedef uint64_t integer;

class prime_sieve { 
 //Простое решето Эратосфена. См. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
public:
 explicit prime_sieve (integer);
 bool is_prime (integer) const;
private:
 vector <bool> is_prime_;
};

inline prime_sieve::prime_sieve (integer limit) {
 limit = max(integer(3), limit);
 is_prime_.resize(limit / 2, true);
 for (integer p = 3; p * p <= limit; p += 2) {
  if (is_prime_[p / 2 - 1]) {
   integer inc = 2 * p;
   for (integer q = p * p; q <= limit; q += inc)
    is_prime_[q / 2 - 1] = false;
  }
 }
}

inline bool prime_sieve::is_prime(size_t n) const {
 if (n == 2) return true;
 if (n < 2 || n % 2 == 0) return false;
 return is_prime_.at(n / 2 - 1);
}

int count_digits(integer n) {
 int digits = 0;
 for (; n > 0; ++digits) n /= 10;
 return digits;
}

integer change_digit (integer n, int index, int new_digit) {
 integer p = 1;
 integer changed = 0;
 for (; index > 0; p *= 10, n /= 10, --index) changed += p * (n % 10);
 changed += (10 * (n / 10) + new_digit) * p;
 return changed;
}

bool unprimeable (const prime_sieve& sieve, integer n) {
 if (sieve.is_prime(n)) return false;
 int d = count_digits(n);
 for (int i = 0; i < d; ++i) {
  for (int j = 0; j <= 9; ++j) {
   integer m = change_digit(n, i, j);
   if (m != n && sieve.is_prime(m)) return false;
  }
 }
 return true;
}

int main() {
 const integer limit = 10000000;
 cout << "Sieve of Eratosthenes calculation, please wait..." << endl;
 prime_sieve sieve (limit);
 ofstream f("unprimeable.txt");
 if (!f) {
  cout << "Can't create unprimeable.txt, check permissions, please" << endl;
  return 1;
 }
 integer n = 200;
 for (; n < limit; ++n) {
  if (unprimeable(sieve, n)) {
   cout << n << endl;
   f << n << endl;
  }
 }
 f.close();
 return 0;
}

 Скачать файл unprimeable.txt в архиве .zip с Яндекс-диска (размер архива 6 Мб)

Кстати, если построить график, показывающий, сколько непростых чисел кратно простому p (на рисунке - для p от 2 до 71), получим почти идеальную зависимость 1/p, сравните с распределением самих простых чисел.

количество непростых чисел, кратных простым

10.10.2021, 00:27 [1064 просмотра]