Разложение на чётнопростые
В этой задаче рассматриваются только чётные целые числа.
Чётное натуральное число 𝑛 будем называть чётнопростым числом, если его нельзя представить в виде произведения двух чётных чисел. Например, числа 2 и 6 — чётнопростые.
Очевидно, что каждое число либо является чётнопростым, либо разлагается в произведение чётнопростых. Но такое разложение на чётнопростые не всегда единственно.
Входные данные
Дано чётное натуральное 𝑛≤10^9.
Выходные данные
Если число 𝑛 чётнопростое, выведите слово prime. Если это число единственным образом разлагается в произведение двух и более чётнопростых, то выведите слово single, а в следующей строке выведите разложение этого числа на чётнопростые множители. Если число допускает несколько различных разложений на чётнопростые, то выведите слово many, а в следующих двух строках выведите два каких-нибудь различных разложения числа на чётнопростые множители.
Примеры
Ввод
6
4
Вывод
prime
single
2 2
Вот мой код:
#include <iostream>
#include <cmath>
using namespace std;
int is_prime(int n) //функция проверки на простоту числа
{
int k = 0;
for (int i = 2; i <= sqrt(n); ++i)
{
if (n % i == 0)
{
return false;
}
}
return !k;
}
int main()
{
int n, k, del1, del2; //n - число с клавиатуры, k - количество 2 в разложении числа
cin >> n;
while (n % 2 == 0)
{
k += 1;
n /= 2;
}
if (k <= 1) cout << "prime"; //если одна 2 в разложении, то prime
else if (n * 4 == 4 && k == 2) //если введённое число - 4(просто чтобы потом с выводом не париться)
{
cout << "single" << endl << 2 << " " << 2;
}
else if (is_prime(n)) // если оставшееся после убирания двоек число простое, то существует только один вариант разложения на чётнопростые
{
cout << "single" << endl << n * 2 << " ";
for (int i = 1; i < k; ++i)
{
cout << 2 << " ";
}
}
else //в другом случае:
{
for (int d = 3; d * d <= n; d += 2)
{
if (n % d == 0)
{
del2 = n / d; // берём первые попавшиеся 2 числителя, чтобы потом вывести 2 возможных разложения
del1 = d;
break;
}
}
cout << "many" << endl << del1 * 2 << " " << del2 * 2 << " ";
for (int i = 2; i < k; ++i)
{
cout << 2 << " ";
}
cout << endl;
cout << n * 2 << " ";
for (int i = 1; i < k; ++i)
{
cout << 2 << " ";
}
}
return 0;
}
На первом же тесте вылезает такая ошибка, хотя, когда я тестил её в компиляторе, её не было. Помогите, пожалуйста, починить код!!
if (n % 4) {
cout << "prime";
} И это всё проверки, необходимые для определения чётнопростого числа.
А вот если оно НЕ чётнопростое, тогда надо двигаться дальше.
Сначала ищем кол-во двоек - как в твоём коде (получая k). А вот дальше получившееся нечётное число раскладываем на простые множители:
map<int, int> t;
int all = 0, i = 3;
while (i * i <= n) {
if (n % i == 0) {
++t[i];
++all;
} else {
i += 2;
}
}
if (n != 1) {
++t[n];
++all;
} Если all <= k - существует единственное разложение на чётнопростые:
for (int i = all; i < k ++i) {
cout << "2 ";
}
for (auto v: t) {
for (int i = 0; i < v.second; ++i) {
cout << v.first * 2 << ' ';
}
} Если all > k - разложений может быть несколько.
P.S. Вверху странички есть поле "Поиск по вопросам". И если ты введёшь там "чётнопростые", то получишь множество вопросов, идентичных твоему, и множество же готовых ответов.
Вот первый тест