Преобразовать число до 0 за наименьшее кол-во шагов

@FoXoDoX · Регистрация: 04.12.2021

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

Нужно заданное число довести до 0, используя следующие шаги:
1. Отнять от числа единичку.
2. Отнять от числа наименьшее простое число, на которое оно может делиться.
Например число 10 преобразуется до 0 за 3 шага:
10 - 2 = 8; 8 - 1 = 7; 7 - 7 = 0.

Не могу написать нормальный код, наиболее оптимальный вариант не находится(например если на входе 1247), можете подсказать хотя бы алгоритм?

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
f = 0
while f != 1:
def prime(n):
if n % 2 == 0: return 2
i = 3
while n % i != 0 and i * i <= n:
i += 2
if i * i <= n: return i
return n
 
health = int(input())
healthf = health
spell = 1
 
while healthf != prime(healthf)
healthf -= 1
 
while health != healthf:
if prime(health) <= health - healthf:
health -= prime(health)
spell += 1
else:
health -= 1
spell += 1
print (health)
 
print(spell)

@iSmokeJC · 19.03.2023, 09:34

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

Отнять от числа наименьшее число, на которое оно может делиться

Это единица, есличо

@thyrex · 19.03.2023, 09:36

iSmokeJC, судя по коду, наименьшее простое нужно отнимать

@FoXoDoX · 19.03.2023, 09:37 **[ТС]**

Упс, извиняюсь, отредактировал условие)

@iSmokeJC · 19.03.2023, 09:39

thyrex,

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

отредактировал условие

Вотъ!

@thyrex · 19.03.2023, 09:47

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

@FoXoDoX · 19.03.2023, 10:18 **[ТС]**

Я так это и сделал, только не получается за минимальное кол-во шагов это сделать. У меня на 1247 получает 7 ходов, а минимум должно быть 5.

@Gdez · 19.03.2023, 11:14

FoXoDoX, исходя из логики примера (10 до 0), 1247 до 0 за три шага:
1247 - 29 = 1218
1218 - 1 = 1217
1217 - 1217 = 0

@thyrex · 19.03.2023, 11:28

Ну вообще минимум получается даже не 5, а 3 (если искать не ближайшее простое)

1247 - 29 - 1 - 1217 = 0

@eaa · 19.03.2023, 11:53

FoXoDoX, ограничения какие?
решай решетом.

@Red white socks · 19.03.2023, 12:02

Проблема Гольдбаха. Ответ: 1, 2 или 3

@rRczZZ · 19.03.2023, 12:06

Red white socks, 4 для 28, 36, 52, 58, 66, 77, ... нет?

@Red white socks · 19.03.2023, 12:17

rRczZZ, в мозгах каша, совсем не в ту степь думал...

@eaa · 19.03.2023, 12:34

дп, тут норм вроде заходит:

Кликните здесь для просмотра всего текста

1000 3
1001 4
1002 4
1003 4
1004 5
1005 5
1006 6
1007 5
1008 6
1009 1
1010 2
1011 3
1012 3
1013 1
1014 2
1015 3
1016 3
1017 3
1018 4
1019 1
1020 2
1021 1
1022 2
1023 3
1024 3
1025 3
1026 4
1027 3
1028 4
1029 5
1030 5
1031 1
1032 2
1033 1
1034 2
1035 3
1036 3
1037 3
1038 4
1039 1
1040 2
1041 3
1042 3
1043 4
1044 4
1045 3
1046 4
1047 5
1048 5
1049 1
1050 2
1051 1
1052 2
1053 3
1054 3
1055 3
1056 4
1057 3
1058 4
1059 5
1060 5
1061 1
1062 2
1063 1
1064 2
1065 3
1066 3
1067 4
1068 4
1069 1
1070 2
1071 3
1072 3
1073 4
1074 4
1075 3
1076 4
1077 5
1078 5
1079 4
1080 5
1081 5
1082 6
1083 6
1084 7
1085 6
1086 7
1087 1
1088 2
1089 3
1090 3
1091 1
1092 2
1093 1
1094 2
1095 3
1096 3
1097 1
1098 2
1099 3
1100 3
1101 3
1102 4
1103 1
1104 2
1105 3
1106 3
1107 3
1108 4
1109 1
1110 2
1111 3
1112 3
1113 3
1114 4
1115 3
1116 4
1117 1
1118 2
1119 3
1120 3
1121 4
1122 4
1123 1
1124 2
1125 3
1126 3
1127 4
1128 4
1129 1
1130 2
1131 3
1132 3
1133 4
1134 4
1135 3
1136 4
1137 5
1138 5
1139 5
1140 6
1141 5
1142 6
1143 7
1144 7
1145 7
1146 8
1147 5
1148 6
1149 7
1150 7
1151 1
1152 2
1153 1
1154 2
1155 3
1156 3
1157 4
1158 4
1159 5
1160 5
1161 5
1162 6
1163 1
1164 2
1165 3
1166 3
1167 3
1168 4
1169 5
1170 5
1171 1
1172 2
1173 3
1174 3
1175 4
1176 4
1177 4
1178 5
1179 5
1180 6
1181 1
1182 2
1183 3
1184 3
1185 3
1186 4
1187 1
1188 2
1189 3
1190 3
1191 3
1192 4
1193 1
1194 2
1195 3
1196 3
1197 3
1198 4
1199 3
1200 4
1201 1
1202 2
1203 3
1204 3
1205 4
1206 4
1207 4
1208 5
1209 5
1210 6
1211 4
1212 5
1213 1
1214 2
1215 3
1216 3
1217 1
1218 2
1219 3
1220 3
1221 3
1222 4
1223 1
1224 2
1225 3
1226 3
1227 3
1228 4
1229 1
1230 2
1231 1
1232 2
1233 3
1234 3
1235 3
1236 4
1237 1
1238 2
1239 3
1240 3
1241 3
1242 4
1243 3
1244 4
1245 5
1246 5
1247 3
1248 4
1249 1
1250 2
1251 3
1252 3
1253 4
1254 4
1255 3
1256 4
1257 5
1258 5
1259 1
1260 2
1261 3
1262 3
1263 3
1264 4
1265 3
1266 4
1267 3
1268 4
1269 5
1270 5
1271 4
1272 5
1273 5
1274 6
1275 6
1276 7
1277 1
1278 2
1279 1
1280 2
1281 3
1282 3
1283 1
1284 2
1285 3
1286 3
1287 3
1288 4
1289 1
1290 2
1291 1
1292 2
1293 3
1294 3
1295 3
1296 4
1297 1
1298 2
1299 3

Добавлено через 2 минуты
+ решето Эратосфена

@rRczZZ · 19.03.2023, 12:59

я вот-такой штукой считал, но без ограничений к задаче непонятно ничего

Кликните здесь для просмотра всего текста

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from math import isqrt
def sieve(n):
    p = [1] * (n+1); p[:2] = 0, 0
    for i in range(2, isqrt(n) + 1):
        if p[i]: p[i*i::i] = [0]*(n//i - i + 1)
    for x in range(n, 0, -1):
        if p[x]: p[x::x] = [x]*(n//x)
    return p
 
limit = 1000000
least = sieve(limit) # least[x] - наименьшее простое, делящее x
sol = [1] * limit; sol[0] = 0
for x in range(2, limit): sol[x] = 1 + min(sol[x-1], sol[x-least[x]])
 
print(sol[1247])

@eaa · 19.03.2023, 13:06

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

Добавлено через 1 минуту
ограничения наверное 10⁶.

YuS_2 · 19.03.2023, 21:22

Не по теме:

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

Это единица, есличо

По непроверенным данным, единицу таки исключили из ряда простых чисел, т.к. она где-то утеряла второй делитель, а кроме того, была замечена в деструктивных действиях, вносящих непоправимые последствия в некоторые стройные теории... за эти грехи её навсегда исключили из "элитного" клуба и поместили в отдельную категорию. :)

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа 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, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	19.03.2023, 09:36
	iSmokeJC, судя по коду, наименьшее простое нужно отнимать 0

@FoXoDoX 0 / 0 / 0 Регистрация: 04.12.2021 Сообщений: 46
	19.03.2023, 09:37 [ТС]
	Упс, извиняюсь, отредактировал условие) 0

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	19.03.2023, 09:47
	FoXoDoX, найти ближайшее простое число, не превосходящее исходное, и сводить к нему 0

@FoXoDoX 0 / 0 / 0 Регистрация: 04.12.2021 Сообщений: 46
	19.03.2023, 10:18 [ТС]
	Я так это и сделал, только не получается за минимальное кол-во шагов это сделать. У меня на 1247 получает 7 ходов, а минимум должно быть 5. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	19.03.2023, 11:14
	FoXoDoX, исходя из логики примера (10 до 0), 1247 до 0 за три шага: 1247 - 29 = 1218 1218 - 1 = 1217 1217 - 1217 = 0 1

@thyrex 14450 / 7489 / 1582 Регистрация: 06.09.2009 Сообщений: 27,133
	19.03.2023, 11:28
	Ну вообще минимум получается даже не 5, а 3 (если искать не ближайшее простое) 1247 - 29 - 1 - 1217 = 0 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	19.03.2023, 11:53
	FoXoDoX, ограничения какие? решай решетом. 2

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	19.03.2023, 12:02
	Проблема Гольдбаха. Ответ: 1, 2 или 3 0

@rRczZZ 814 / 422 / 169 Регистрация: 08.02.2013 Сообщений: 711
	19.03.2023, 12:06
	Red white socks, 4 для 28, 36, 52, 58, 66, 77, ... нет? 2

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	19.03.2023, 12:17
	rRczZZ, в мозгах каша, совсем не в ту степь думал... 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	19.03.2023, 12:34
	дп, тут норм вроде заходит: Кликните здесь для просмотра всего текста 1000 3 1001 4 1002 4 1003 4 1004 5 1005 5 1006 6 1007 5 1008 6 1009 1 1010 2 1011 3 1012 3 1013 1 1014 2 1015 3 1016 3 1017 3 1018 4 1019 1 1020 2 1021 1 1022 2 1023 3 1024 3 1025 3 1026 4 1027 3 1028 4 1029 5 1030 5 1031 1 1032 2 1033 1 1034 2 1035 3 1036 3 1037 3 1038 4 1039 1 1040 2 1041 3 1042 3 1043 4 1044 4 1045 3 1046 4 1047 5 1048 5 1049 1 1050 2 1051 1 1052 2 1053 3 1054 3 1055 3 1056 4 1057 3 1058 4 1059 5 1060 5 1061 1 1062 2 1063 1 1064 2 1065 3 1066 3 1067 4 1068 4 1069 1 1070 2 1071 3 1072 3 1073 4 1074 4 1075 3 1076 4 1077 5 1078 5 1079 4 1080 5 1081 5 1082 6 1083 6 1084 7 1085 6 1086 7 1087 1 1088 2 1089 3 1090 3 1091 1 1092 2 1093 1 1094 2 1095 3 1096 3 1097 1 1098 2 1099 3 1100 3 1101 3 1102 4 1103 1 1104 2 1105 3 1106 3 1107 3 1108 4 1109 1 1110 2 1111 3 1112 3 1113 3 1114 4 1115 3 1116 4 1117 1 1118 2 1119 3 1120 3 1121 4 1122 4 1123 1 1124 2 1125 3 1126 3 1127 4 1128 4 1129 1 1130 2 1131 3 1132 3 1133 4 1134 4 1135 3 1136 4 1137 5 1138 5 1139 5 1140 6 1141 5 1142 6 1143 7 1144 7 1145 7 1146 8 1147 5 1148 6 1149 7 1150 7 1151 1 1152 2 1153 1 1154 2 1155 3 1156 3 1157 4 1158 4 1159 5 1160 5 1161 5 1162 6 1163 1 1164 2 1165 3 1166 3 1167 3 1168 4 1169 5 1170 5 1171 1 1172 2 1173 3 1174 3 1175 4 1176 4 1177 4 1178 5 1179 5 1180 6 1181 1 1182 2 1183 3 1184 3 1185 3 1186 4 1187 1 1188 2 1189 3 1190 3 1191 3 1192 4 1193 1 1194 2 1195 3 1196 3 1197 3 1198 4 1199 3 1200 4 1201 1 1202 2 1203 3 1204 3 1205 4 1206 4 1207 4 1208 5 1209 5 1210 6 1211 4 1212 5 1213 1 1214 2 1215 3 1216 3 1217 1 1218 2 1219 3 1220 3 1221 3 1222 4 1223 1 1224 2 1225 3 1226 3 1227 3 1228 4 1229 1 1230 2 1231 1 1232 2 1233 3 1234 3 1235 3 1236 4 1237 1 1238 2 1239 3 1240 3 1241 3 1242 4 1243 3 1244 4 1245 5 1246 5 1247 3 1248 4 1249 1 1250 2 1251 3 1252 3 1253 4 1254 4 1255 3 1256 4 1257 5 1258 5 1259 1 1260 2 1261 3 1262 3 1263 3 1264 4 1265 3 1266 4 1267 3 1268 4 1269 5 1270 5 1271 4 1272 5 1273 5 1274 6 1275 6 1276 7 1277 1 1278 2 1279 1 1280 2 1281 3 1282 3 1283 1 1284 2 1285 3 1286 3 1287 3 1288 4 1289 1 1290 2 1291 1 1292 2 1293 3 1294 3 1295 3 1296 4 1297 1 1298 2 1299 3 Добавлено через 2 минуты + решето Эратосфена 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	19.03.2023, 13:06
	rRczZZ, я так же решал. только минимальный простой делитель можно вычислять за один проход по решету. Добавлено через 1 минуту ограничения наверное 10⁶. 0

Преобразовать число до 0 за наименьшее кол-во шагов

Решение