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

@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)

Новые блоги и статьи Все статьи Все блоги /
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .

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

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