Задача "Просто"

@Artem0303 · Регистрация: 25.05.2020

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

Дано целое число n. Представьте его в виде суммы простых чисел. Если есть k слагаемых, то ответ должен быть в формате a 1 + a 2 + ... + a k(Без пробелов). Среди всех таких строк, ваша ответ должен быть лексикографично минимальным. Строка a считается лексикографично меньше строки b, если выполняется по крайней мере одно условие:
• a это префикс b, но длина b большая длины a, например, строка abc является лексикографично меньше abcd;
• существует такая позиция p, что a₁ = b₁ , a₂ = b₂ , ..., a_p-1 = b_p-1 , а также a_p <b_p , например, строка abbc является лексикографично меньше abca. Символ "+" лексикографично меньше символов цифр.

Формат входных данных
Первая строка содержит одно целое число n (2 ≤ n ≤ 9 · 10¹⁸ ).

Формат выходных данных
Выведите одну строку.

Примеры
standart input////////////////standart output
2//////////////////////////////2
5//////////////////////////////2+3

@Semen-Semenich · 31.10.2020, 14:13

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def IsPrime(n):
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    return d * d > n
 
def list_prime(n):
    return [ i for i in range(2, n+1) if IsPrime(i)]
    
n = int(input())
lst = list_prime(n)
for num in lst:
    x = n - num
    if x in lst:
        print(f'{num} + {x}')
        break

возможно даже эту строку

Python
1
return [ i for i in range(2, n+1) if IsPrime(i)]

написать поиск в половине диапазона

Python
1
return [ i for i in range(2, n//2) if IsPrime(i)]

но это не точно и надо проверить

@eaa · 31.10.2020, 14:40

для четного ответ:
2+...+2
для нечетного ответ:
2+..+2+3

Или что-то я не понял?

Добавлено через 10 минут
а нет.
есть же простые числа которые начинаются на 1.

@Gdez · 31.10.2020, 15:00

Semen-Semenich, если нечетное и не простое, минус 3 в начале

Добавлено через 15 минут
Или условия не понял - поиск простого числа до 10^19 ?

@eaa · 31.10.2020, 15:23

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

поиск простого числа до 10^19

да.

тут решение быстрое: препроцессинг + жадный алгоритм

Добавлено через 22 минуты
хотя препроцессинг можно зашить в программу, тоже быстро считает.

@eaa · 01.11.2020, 19:17

Gdez, ну что, где решение? или это не школьная олимпиада?))

@Gdez · 01.11.2020, 20:09

eaa,

или это не школьная олимпиада?))

Не знаю...
ТС пропал. По условию - я понял его так - нужно представить чмсло в виде суммы простых чисел в порядке возрастания и их количество должно быть минимальным. При равенстве слагаемых вывести набор с минимальным первым.
При таких условиях я не знаю, как решить - 10^18 очень много - любое число можно представить в виде суммы максимум трех простых чисел.

@Semen-Semenich · 02.11.2020, 17:53

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def isprime(n):
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    return d * d > n
 
 
a = []
 
while True:
   b = int(input("Введите число: "))
   if b < 2:
       print("Числа должны быть быльше 1.")
   elif b >= 2:
       a.append(b)
   exit = input("Для начала проверки числе нажмите 'F':" )
   if exit.lower() == "f":
       print(a)
       break
 
for i in a:
    if isprime(i):
        print(i)

Новые блоги и статьи Все статьи Все блоги /
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .

@Artem0303 0 / 0 / 0 Регистрация: 25.05.2020 Сообщений: 17

	Задача "Просто" 31.10.2020, 12:50. Показов 2089. Ответов 7 Метки нет (Все метки) Дано целое число n. Представьте его в виде суммы простых чисел. Если есть k слагаемых, то ответ должен быть в формате a 1 + a 2 + ... + a k(Без пробелов). Среди всех таких строк, ваша ответ должен быть лексикографично минимальным. Строка a считается лексикографично меньше строки b, если выполняется по крайней мере одно условие: • a это префикс b, но длина b большая длины a, например, строка abc является лексикографично меньше abcd; • существует такая позиция p, что a₁ = b₁ , a₂ = b₂ , ..., a_p-1 = b_p-1 , а также a_p <b_p , например, строка abbc является лексикографично меньше abca. Символ "+" лексикографично меньше символов цифр. Формат входных данных Первая строка содержит одно целое число n (2 ≤ n ≤ 9 · 10¹⁸ ). Формат выходных данных Выведите одну строку. Примеры standart input////////////////standart output 2//////////////////////////////2 5//////////////////////////////2+3 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	31.10.2020, 14:40
	для четного ответ: 2+...+2 для нечетного ответ: 2+..+2+3 Или что-то я не понял? Добавлено через 10 минут а нет. есть же простые числа которые начинаются на 1. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	31.10.2020, 15:00
	Semen-Semenich, если нечетное и не простое, минус 3 в начале Добавлено через 15 минут Или условия не понял - поиск простого числа до 10^19 ? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	01.11.2020, 19:17
	Gdez, ну что, где решение? или это не школьная олимпиада?)) 0

Задача "Просто"

Решение