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

@Ingalsar · Регистрация: 12.07.2023

Студворк — интернет-сервис помощи студентам

Разложение на чётнопростые
В этой задаче рассматриваются только чётные целые числа.

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

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

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

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

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

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

Примеры
6
prime
4
single
2 2

@Doule_ · 13.07.2023, 23:16

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
v = set()
for i in range(2, n, 2):
    for k in range(2, n, 2):
        if i * k == n:
            v.add(tuple(sorted([i, k])))
    if len(v) > 1:
        print('many')
        break
if len(v) == 1:
    print('single')
if not v:
    print('prime')
else:
    for i in v:
        print(*i)

@idealist · 14.07.2023, 00:55

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from math import isqrt, prod
n = int(input('n = '))
 
_2_div = []
s_div = []
for i in range(2, isqrt(n) + 2):
    if n == 1:
        break
    while n % i == 0:
        if i == 2:
            _2_div.append(i)
        else:
            s_div.append(i)
        n //= i
if n > 1:
    s_div.append(n)
s_div_L = s_div[:len(_2_div) - 1]
s_div_R = s_div[len(_2_div) - 1:]
 
if len(_2_div) == 1:
    print('prime')
elif len(_2_div) - len(s_div) >= 1:
    print('single')
    arr = [2] * (len(_2_div) - len(s_div))
    if s_div:
        arr.extend([x * 2 for x in s_div])
    print(*arr)
else:
    print('many')
    arr_1 = s_div_L + [prod(s_div_R)]
    arr_1 = [x * 2 for x in arr_1]
    print(*arr_1)
 
    arr_2 = arr_1
    arr_2[0] //= s_div[0]
    arr_2[1] *= s_div[0]
    print(*arr_2)

Doule_, у вас сложность квадратичная, а числа большие, может по скорости не пройти.

И разлагать должна на четнопростые множители, а у вас пока так:

Python
1
2
3
4
n = 1000
many
2 500
4 250

@idealist · 14.07.2023, 10:19

Еще вариант:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from math import isqrt
n = int(input('n = '))
if n % 4:
    print('prime')
else:
    es_div = []
    for i in range(3, isqrt(n) + 2, 2):
        if n == 1:
            break
        while n % i == 0:
            if n % 4 == 0:
                es = i*2
            else:
                es = n
            es_div.append(es)
            n //= es
    while n % 2 == 0:
        if n % 4 == 0:
            es = 2
        else:
            es = n
        es_div.append(es)
        n //= es
 
    if 2 in es_div:
        print('single')
        print(*es_div)
    else:
        print('many')
        print(*es_div)
        k = es_div[0] // 2
        es_div[0] //= k
        es_div[1] *= k
        print(*es_div)

@idealist · 14.07.2023, 21:14

Пардон, в решение вкралась ошибка. Неверно определяются типы single и many.
Вот так правильно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from math import isqrt
n = int(input('n = '))
if n % 4:
    print('prime')
else:
    es_div = []
    for i in range(3, isqrt(n) + 2, 2):
        if n == 1:
            break
        while n % i == 0:
            if n % 4 == 0:
                es = i * 2
            else:
                es = n
            es_div.append(es)
            n //= es
    while n % 2 == 0:
        if n % 4 == 0:
            es = 2
        else:
            es = n
        es_div.append(es)
        n //= es
 
    if len(es_div) - es_div.count(2) <= 1:
        print('single')
        print(*es_div)
    else:
        print('many')
        print(*es_div)
        k = es_div[0] // 2
        es_div[0] //= k
        es_div[1] *= k
        print(*es_div)

Добавлено через 1 час 50 минут
Да, вот чувствовал, что я что-то не додумал в этой задаче. Нашел толковое решение у Red white socks вот здесь и кое-что изменил по своему вкусу.
Оказывается можно находить только один наименьший простой делитель, и этого достаточно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from math import isqrt
def min_prime(n):
    for i in range(3, isqrt(n) + 2, 2):
        if n % i == 0:
            return i
    else:
        return n
 
n = int(input('n = '))
es_div = []
while n % 2 == 0:
    es_div.append(2)
    n //= 2
es_div[-1] *= n
d = min_prime(n)
 
if len(es_div) == 1:
    print('prime')
elif d == n:
    print('single')
    print(*es_div)
else:
    print('many')
    print(*es_div)
    es_div[-2] *= d
    es_div[-1] //= d
    print(*es_div)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@Ingalsar 0 / 0 / 0 Регистрация: 12.07.2023 Сообщений: 23

	Разложение на чётнопростые (Сириус) 13.07.2023, 20:43. Показов 1669. Ответов 4 Метки нет (Все метки) Разложение на чётнопростые В этой задаче рассматриваются только чётные целые числа. Чётное натуральное число n будем называть чётнопростым числом, если его нельзя представить в виде произведения двух чётных чисел. Например, числа 2 и 6 — чётнопростые. Очевидно, что каждое число либо является чётнопростым, либо разлагается в произведение чётнопростых. Но такое разложение на чётнопростые не всегда единственно. Входные данные Дано чётное натуральное n≤109 . Выходные данные Если число n чётнопростое, выведите слово prime. Если это число единственным образом разлагается в произведение двух и более чётнопростых, то выведите слово single, а в следующей строке выведите разложение этого числа на чётнопростые множители. Если число допускает несколько различных разложений на чётнопростые, то выведите слово many, а в следующих двух строках выведите два каких-нибудь различных разложения числа на чётнопростые множители. Примеры 6 prime 4 single 2 2 0