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

@Manichka · Регистрация: 10.06.2020

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

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

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

@Matrix3007 · 12.06.2020, 14:18

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ch(x):
    if x % 4 == 0:
        c=0
        for i in range(x-1):
            if i % 2 == 0 and i % 4 != 0 and x % i == 0:
                c+=1
        if c>=3:
            return "many"
        else:
            return "single"
    elif x % 2 == 0:
        return "prime"
        
print(ch(int(input())))

@MaxRazgonyaev · 12.06.2020, 15:50

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
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:
  solve(int(line))

Добавлено через 12 минут
Matrix3007, У вас, если "single", не выводит в следующей строке разложение на чётнопростые.

@Matrix3007 · 12.06.2020, 17:23

MaxRazgonyaev, У меня и на "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
def ch(x):
    if x % 4 == 0:
        c=0
        a=[]
        for i in range(x-1):
            if i % 2 == 0 and i % 4 != 0 and x % i == 0:
                c+=1
                a.append(i)
        b=[]
        r=[]
        for i in range(len(a)):
            if a[i] not in b:
                e=x
                d=0
                while e not in a:
                    e/=a[i]
                    d+=1
            r.append((str(a[i])+" * ")*d+str(int(e)))
            b.append(e)
        if c>=3:
            return "many\n"+str(r[0])+"\n"+str(r[1])
        else:
            return "single\n"+str(r[0])
    elif x % 2 == 0:
        return "prime"
        
print(ch(int(input())))

Добавлено через 44 минуты
Некоторые числа западали на while. Исправил:

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
def ch(x):
    if x % 4 == 0:
        c=0
        a=[]
        for i in range(x-1):
            if i % 2 == 0 and i % 4 != 0 and x % i == 0:
                c+=1
                a.append(i)
        b=[]
        r=[]
        for i in range(len(a)):
            if a[i] not in b:
                e=x
                d=0
                while e not in a and e % a[i] == 0:
                    e/=a[i]
                    d+=1
            r.append((str(a[i])+" * ")*d+str(int(e)))
            b.append(e)
        if c>=3:
            return "many\n"+str(r[0])+"\n"+str(r[1])
        else:
            return "single\n"+str(r[0])
    elif x % 2 == 0:
        return "prime"
        
print(ch(int(input())))

@Alex_qd · 13.06.2020, 11:29

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
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)))
 
solve(int(input())

@Евгнений · 29.06.2020, 21:54

Сообщение от Alex_qd

while not (n&1):

А что значит эта строка?
Я никогда не сталкивался с &.

@Infeeqs · 29.06.2020, 22:31

Евгнений, это значит объединение, не переживайте я тоже вот столкнулся и сразу всё понял прочтите документацию и всё поймёте.
с наилучшими пожеланиями, про кодер.

@iSmokeJC · 29.06.2020, 22:37

Сообщение от Infeeqs

это значит объединение

Ты вообще все от фонаря пишешь?

@Infeeqs · 29.06.2020, 22:38

iSmokeJC, я стараюсь помочь людям разве это не символ объединения?!

Добавлено через 33 секунды
в c# помню точно это он был

Добавлено через 7 секунд
да и тут должен

@iSmokeJC · 29.06.2020, 22:40

Infeeqs, помочь - это, конечно, похвально.
Но для этого самому нужно что-то знать. Вот ты не уверен в этом операторе, а уже туда же с советами.
Для начала, как минимум, загуглил бы что он значит в питоне. (Да и не только в питоне)

@Евгнений · 30.06.2020, 09:08

Сообщение от Евгнений

&

Я уже понял.
это побитовое И.
И можно было написать

Python
1
while n%2==0:

@Fedor11 · 19.07.2021, 14:25

у меня так только не пойму в чём проблема, вроде все заковыристые примеры проходит.

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
38
39
40
41
42
43
n = int(input())
 
dl = []
d = 2
while d * d <= n:
    if n % d == 0:
        dl.append(d)
        n //= d
    else:
        d += 1
if n > 1:
    dl.append(n)
 
amount_2 = dl.count(2)
len_dl = len(dl)
res = list()
s = 1
 
if amount_2 == 1:
    print('prime')
    quit()
 
if len_dl - amount_2 <= 1:
    print('single')
    for i in range(amount_2 - (len_dl - amount_2)):
        res.append(2)
    for i in range(amount_2, len_dl):
        res.append(dl[i - amount_2] * dl[i])
    print(*res)
else:
    print('many')
    res_1 = []
    res_2 = []
    for i in range(amount_2 - (len_dl - amount_2)):
        res_1.append(2)
    for i in range(amount_2, len_dl):
        res_1.append(dl[i - amount_2] * dl[i])
        s *= dl[i]
        # res_2.append(dl[i - amount_2] * dl[len_dl + amount_2 - i - 1])
    res_2 = [2] * (amount_2 - 1)
    res_2.append(s*2)
    print(*res_1)
    print(*res_2)

Добавлено через 3 минуты
а где можно эту задачу с тестами проверить что бы было видно сколько проходит? типо informatics или acmp?

@Tarr Garrad Rin · 19.07.2021, 17:57

Допустим я удалил сообщение

@bami-lil · 16.08.2022, 13:06

что не так с программой?

Python
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input()) 
if n % 4 != 0: 
  print('prime') 
  exit() 
k, i = n // 4, 2 
while i * i <= k: 
  if k % i == 0: 
    print('many\n2 %d\n%d %d' % (n // 2, 2 * i, n // (2 * i))) 
    break 
  i += 1 
else: 
  print('single\n2', n // 2)

Новые блоги и статьи Все статьи Все блоги /
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .	[golang] Worker Pool alhaos 09.06.2026 Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .	Свет внутри себя kumehtar 07.06.2026 Пусть это будет здесь lIs4oanZS9Y	Программа для com-порта Uhbif79 05.06.2026 Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .	Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .

@Manichka 1 / 1 / 0 Регистрация: 10.06.2020 Сообщений: 19

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

@Infeeqs 8 / 8 / 0 Регистрация: 15.02.2020 Сообщений: 195
	29.06.2020, 22:31
	Евгнений, это значит объединение, не переживайте я тоже вот столкнулся и сразу всё понял прочтите документацию и всё поймёте. с наилучшими пожеланиями, про кодер. 0

@Infeeqs 8 / 8 / 0 Регистрация: 15.02.2020 Сообщений: 195
	29.06.2020, 22:38
	iSmokeJC, я стараюсь помочь людям разве это не символ объединения?! Добавлено через 33 секунды в c# помню точно это он был Добавлено через 7 секунд да и тут должен 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	29.06.2020, 22:40
	Infeeqs, помочь - это, конечно, похвально. Но для этого самому нужно что-то знать. Вот ты не уверен в этом операторе, а уже туда же с советами. Для начала, как минимум, загуглил бы что он значит в питоне. (Да и не только в питоне) 0

@Tarr Garrad Rin 0 / 0 / 0 Регистрация: 19.07.2021 Сообщений: 1
	19.07.2021, 17:57
	Допустим я удалил сообщение 0