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

Question

Всем здравствуйте! Никак не получается решить одну задачу.

Условие задачи:
В этой задаче рассматриваются только чётные целые числа. Чётное натуральное число ? будем называть чётнопростым числом, если его нельзя представить в виде произведения двух чётных чисел. Например, числа 2 и 6 — чётнопростые. Очевидно, что каждое число либо является чётнопростым, либо разлагается в произведение чётнопростых. Но такое разложение на чётнопростые не всегда единственно.

Входные данные:
Дано чётное натуральное ? ≤ 10⁹.

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

Мой код:

def even_prime_check(n): # проверка числа на чётно-простоту
    if n%4 == 0:
        return False
    else:
        return True

def even_prime_factorization(n): # функция для не чётно-простого числа
    a = []
    b = []
    a.append(n//2)
    a.append(2)
    check1 = a[0]
    check2 = a[1]

    for d in range(6,10**6,4):
        if n%d == 0 and even_prime_check(n//d) and n//d != check2 and d != check1:
            b.append(n//d)
            b.append(d)
            break

    return a,b

n = int(input())
a,b = even_prime_factorization(n)

if even_prime_check(n):
    print('prime')

elif len(a) == 2 and len(b) == 0:
    print('single')
    print(' '.join(map(str, a)))

elif len(a) == 2 and len(b) == 2:
    print('many')
    print(' '.join(map(str, a)))
    print(' '.join(map(str, b)))

Я тестирую эту программу, вроде всё верно. Но моё решение засчитывается как неверное. Помогите, пожалуйста, найти ошибку и исправить код.

Answer 1

int main()
{
    int n;
    cin >> n;
    if (n%4)                // Если не делится на 4 - выводим, что простое
    {
        cout << "prime\n";
        return 0;
    }
    int two = 0;            // Считаем степень 2 в разложении
    while(n%2 == 0)         // пока делится на 2 - 
    {
        two++;              // увеличиваем показатель
        n /= 2;             // само число делим на 2
    }
    vector<int> ps;         // Здесь массив нечетных простых делителей

    for(int d = 3; n > 1 && d*d <= n; d+=2)   // Для всех нечетных делителей от 3
    {                         // и до корня из n, с шагом 2
        while(n%d == 0)       // Пока делится (и если делится) на d
        {
            ps.push_back(d);  // вносим в массив
            n /= d;           // и делим на d
        }
    }
    if (n > 1) ps.push_back(n);  // Все что осталось простого - тоже в массив

    if (ps.size() <= 1)   // Если только один нечетный множитель - ответ 2 2 2... 2*d
    {                     // если его нет - просто двойки
        cout << "single\n";
        for(int i = 0; i < two-1; ++i) cout << "2 ";  // Выводим двойки
        cout << (ps.size()==0 ? 2 : 2*ps[0]) << endl; // Последний элемент - 2 или 2d, если есть
    }
    else
    {
        cout << "many\n";
        // Пусть в массиве простых нечетных делителей - d0 d1 d2...
        // Тогда первая выводимая строка - 2 2 .. 2 2*d0 2*d1*d2...

        for(int i = 0; i < two-2; ++i) cout << "2 ";
        cout << 2*ps[0] << " ";        // Это и есть 2*d0
        n = 1;  // Тут будет d1*d2...
        for(int i = 1; i < ps.size(); ++i) n *= ps[i];  // Перемножили
        cout << 2*n << endl;                            // Вывели 2*d1*d2...

        // Второй вывод - 2 2 .. 2 2 2*d0*d1*d2...
        for(int i = 0; i < two-1; ++i) cout << "2 ";    // Вывели двойки
        cout << 2*n*ps[0] << endl;                      // Вывели 2*d0*d1*d2...
    }
}

Все это благополучно проходит тестовую систему.. Весь код - https://ideone.com/otGj84

Answer 2

https://ideone.com/jlfdZu

def solve(n):
  d = 0
  while not (n&1):
    d += 1
    n //= 2

  a = [2]*d
  a[-1] *= n

  if d == 1:
    print("prime")
    return

  for x in range(3, int(n**.5)+1, 2):
    if not (n%x):
      b = a[:]
      b[-1] //= x
      b[-2] *= x
      print("many")
      print(" ".join(map(str, a)))
      print(" ".join(map(str, b)))
      return

  print("single")
  print(" ".join(map(str, a)))

from sys import stdin

for line in stdin:
  print("=== " + line.strip() + " ===")
  solve(int(line))

БЛОГ НА HUSL

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

Ответы (2 шт):