Элементы теории чисел

В прошлой статье мы уже затрагивали такое понятие, как простые числа. Сегодня я предлагаю подробнее поговорить про факторизацию числа (разложение на простые множители) и про делители числа.

Согласно основной теореме арифметики каждое натуральное число может быть представлено как произведение простых чисел. Например, число 12 мы можем представить следующим образом:

\[12 = 2 * 2 * 3\] \[12 = 2^2 * 3^1\]

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

\[x = p_1^{\alpha_1} * p_2^{\alpha_2} * \ldots * p_n^{\alpha_n} = \prod\limits_i {p_i^{\alpha_i}}\]

Проверка числа на простоту

Чтобы проверить, является ли натуральное число x простым, достаточно просто проверить, существует ли в отрезке \([2;\sqrt{x}]\) число, которое делится на x. В чем смысл? Если бы существовало такое число y, что x делится на y и \(\sqrt x < y < x\), то гарантированно существовало бы и число \(z=x/y\), которое было бы меньше корня, а значит, изначального условия хватило бы для проверки на простоту.

int n = 11;
for (int i = 2; i<= sqrt(n);i++)
	if (n % i == 0)
	{
		cout << "The number is composite";
		return 0;
	}
cout << "The number is prime";
return 0;

Факторизация

Как уже упоминалось ранее - факторизация - разложение числа на простые множители. Принцип работы следующего алгоритма мало чем отличается от предыдущего - нужно перебрать все числа в промежутке \([2; \sqrt x]\), и попытаться разделить x на каждое из них по очереди.

int n = 24;
vector <int> factors;
for (int i = 2; i < sqrt(n); i++)
{
	while (n % i == 0)
	{
		factors.push_back(i);
		n = n / i;
	}
}
if (n != 1)
	factors.push_back(n);
for (auto i : factors)
	cout << i << " ";
return 0;

Поиск делителей

Еще одной часто встречающейся задачей в олимпиадном программировании является поиск делителей. Под делителями числа подразумевают все числа, на которые оно делится. Так, делители 24: 1,2,3,4,6,8,12,24.

int n = 24;
vector <int> deviders;
for (int i = 1; i <= sqrt(n); i++)
{
	if (n % i == 0)
	{
		deviders.push_back(i);
		if (i * i != n)
			deviders.push_back(n / i);
	}
}
	
for (auto i : deviders)
	cout << i << " ";
return 0;