Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Разложение на чётнопростые

Александр Кротов Ученик (187), на голосовании 2 месяца назад
В этой задаче рассматриваются только чётные целые числа.

Чётное натуральное число ? будем называть чётнопростым числом, если его нельзя представить в виде произведения двух чётных чисел. Например, числа 2 и 6 — чётнопростые.

Очевидно, что каждое число либо является чётнопростым, либо разлагается в произведение чётнопростых. Но такое разложение на чётнопростые не всегда единственно.

Входные данные

Дано чётное натуральное ?≤109.

Выходные данные

Если число ? чётнопростое, выведите слово prime. Если это число единственным образом разлагается в произведение двух и более чётнопростых, то выведите слово single, а в следующей строке выведите разложение этого числа на чётнопростые множители. Если число допускает несколько различных разложений на чётнопростые, то выведите слово many, а в следующих двух строках выведите два каких-нибудь различных разложения числа на чётнопростые множители.

Примеры

Ввод
Вывод
6
prime
4
single
2 2

Вот мой код:
 #include  
#include
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;
}
На первом же тесте вылезает такая ошибка, хотя, когда я тестил её в компиляторе, её не было. Помогите, пожалуйста, починить код!!
Голосование за лучший ответ
Jurijus Zaksas Искусственный Интеллект (445776) 3 месяца назад
Чувак, число, которое можно представить в виде произведения двух четных чисел, без остатка делится на 4. Если такой способ не единственный, оно делится на 8. Начни с этого, и твой код станет гораздо проще, а места для ошибок - гораздо меньше.
Александр КротовУченик (187) 3 месяца назад
Вы не правы, число 8 делится на 8, но у него единственный вариант разложения - 2 * 2 * 2
Jurijus Zaksas Искусственный Интеллект (445776) А чо, 2х4 уже не 8?
Александр КротовУченик (187) 3 месяца назад
4 = 2 * 2
Jurijus Zaksas Искусственный Интеллект (445776) Ладно, исключи целые степени двойки тогда.
Похожие вопросы