Разложение на простые множители для первых 10000000 чисел

Знаете ли вы, что 2*2*2*2*2*5*5*5*5*5 равно ровно 100000?
А это очевидно, если понимать, что у нас всего 10 цифр.
(не помню, откуда)

Перечитывал биографию Эйлера. Много думал :)

"Маркиз Кондорсе вспоминал, что вскоре после переезда в Берлин (из России - прим. моё) Эйлера пригласили на придворный бал. На вопрос королевы-матери, отчего он так немногословен, Эйлер ответил: «Я приехал из страны, где, кто разговаривает, того вешают»."

В 1741-м сказано-с :) (из вчерашнего)

Приписанная Пифагору тотальная нумерология в стиле "мир есть число" нуждается лишь в одном уточнении - а что это, собственно, за число?
Натуральное оно или вещественное, рациональное или, что вероятнее, иррациональное? А может, комплексное, как был уверен мой преподаватель по ТФКП?
Поскольку, оставаясь хотя бы частично в своём уме, ответ на этот вопрос дать невозможно, нужно заменять одно-единственное Число Мира Последовательностями, какая-то из которых наверняка указывает направление к недостижимой истине, правда, всё равно не приведёт к ней, потому что неверны сами условия поиска.
Это только падший мир, из которого ушло живое Слово, действительно есть число.
А когда имеется правильное Слово, да на вас из-за него ещё и не завели дело, то математика становится излишней...
(из сна)

Возможно, я просто не нашёл сейчас в своём блоге реализации основной теоремы арифметики, то есть, разложения натурального числа n>1 на простые множители.

Такое разложение (факторизация) единственно с точностью до порядка следования множителей. Можно сказать, что простые числа - это элементарные "строительные блоки", из которых конструируются все остальные числа.

Думаю, функция primeFactors из показанного ниже кода ещё может пригодиться. Программа написана на консольном C++ и проверена в текущей сборке Visual Studio 2019.

Решето Эратосфена взято отсюда. Так как простые числа факторизовать не нужно, они выводятся в файл "как есть". Каждые 100000 шагов в консоль печатается числовая отметка.

Далее показан листинг программы и прикреплён архив .zip с файлом factorization.txt, в каждой строке которого содержится либо единственное число (если оно простое), либо его разложение на простые множители в форме записи вида 2*5*23*2749=632270, так что результат легко пересчитать, например, в Excel или в строке поиска Google.

#include <iostream>
#include <fstream>
#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);
}

void primeFactors(integer n, std::vector<integer>& r) {
 //Основная функция, пишет простые множители числа n в вектор r
 int f = 2; 
 if (n == 1) r.push_back(1);
 else {
  while (true) {
   if (!(n % f)) {
    r.push_back(f);
    n /= f; 
    if (n == 1) return;
   }
   else f++;
  }
 }
}

int main() {
 vector <integer> pf;
 integer n;
 const integer limit = 10000000; //Верхняя граница поиска
 cout << "Sieve of Eratosthenes calculation, please wait..." << endl;
 prime_sieve sieve(limit);
 ofstream f("factorization.txt");
 if (!f) {
  cout << "Can't create factorization.txt, check permissions, please" << endl;
  return 1;
 }
 //Основной цикл:
 for (n = 2; n <= limit; n++) {
  if (sieve.is_prime(n)) { 
   f << n << endl; //Простые числа выводим "как есть"
   continue; 
  }
  primeFactors(n, pf);
  for (auto i = pf.begin(); i != pf.end(); i++) {
   f << *i << (i == pf.end() - 1 ? '=' : '*');
  }
  f << n << endl;
  if (n%100000==0) cout << n << ' ';
  pf.clear();
 }
 f.close();
 cout << "Done. See factorization.txt";
 return 0;
}

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

 Развитие темы: большие проблемы

14.10.2021, 05:36 [669 просмотров]