Требуется написать программу для разложения числа на простые множители. Мой вариант не проходит последний тест из 4. В чем ошибка?
Задачка из Yandex.Handbook на циклы (Python). Требуется составить математическое выражение — произведение простых неубывающих чисел, которое в результате даёт исходное. Мой код проходит три теста из четырех. Последний тест возвращает ошибку «Ответ неверен. Ошибка в программе, либо неверный алгоритм». Не могу понять, где проблема.
number = int(input()) def is_simple(number): counter = 0 if number % 2 == 0: return 'NO' else: for i in range(3, number + 1, 2): if number % i == 0: counter += 1 if counter > 1: break if counter == 1: return 'YES' else: return 'NO' devider = [2, 3, 5, 7] devider_list = [] i = 0 while i < len(devider): if is_simple(number) != 'YES': if number % devider[i] == 0: number = int(number / devider[i]) devider_list.append(devider[i]) else: i = i + 1 else: break devider_list.append(number) my_lst_str = ' * '.join(map(str, devider_list)) print(my_lst_str)- Вопрос задан 06 июл. 2023
- 258 просмотров
1 комментарий
Простой 1 комментарий
Питон. разложить нат. число на простые множители
можно. вместо slist.append(s) написать print(s). А последнюю строчку затереть. Или как предложил etojan.
Вот пожалуйста, разложение на множители числа 12345678912345678912 по мнению курильщика: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 11157689, 60029989]
а можно решение без списков
Да, но float представляет все целые числа без погрешности только до 2^52, на больших числах твой код не будет всегда работать, потому что n при первом же делении станет типа float, а не int
мы туда попадём только если выполнится условие выше n % s == 0
div = 2 # претендент на делитель
if num % div == 0: # остаток от деления равен нулю
print(div) # печатаем делитель
num //= div # делим исходное число на делитель, чтоб искать дальше
continue # проверяем еще раз, будет ли делиться снова на этот же делитель
if div > num**.5 + 1: # если делитель уже больше, чем корень из n
print(num) # то единственным таким делителем может быть только само n
div += 1 # если не делится - увеличиваем возможный делитель
Пожалуйста, запустите хоть раз для сравнения моё решение и ваше, после чего убедитесь в моей правоте и давайте закрывать этот спор. Местные ыксперты всё равно считают ваше решение лучшим
Уважаемый профессор, в CPython, который является стандартным интерпретатором для языка Python, числа Int имеют максимальную длину размера выделенной для интерпретатора памяти. В некоторых компиляторах, действительно, они могут быть ограничены 32 или 64 битами, но по умолчанию в них подключена длинная арифметика.
etojan, вы всё слишком усложняете. Вы используете вводимое число типа Int. Не знаю скольки битная у Вас система, но значения это типа Int32: [-2147483648,2147483647]
Int64: [-9223372036854775808,9223372036854775807]. Для чего брать значения выходящие за диапазон данного типа?!
etojan, разложение на множители числа 12345678912345678912. 2
2
2
2
2
2
3
313
35129
Произведение будет = 2111112384.
Разложить число на простые множители
Да и для while никакого условия не нужно, т.е. просто while true (ну или do , если такое есть в питоне). Иначе этот код на обычную тройку ничего не выведет.
30 мар 2017 в 9:32
5 ответов 5
Сортировка: Сброс на вариант по умолчанию
Одна из реализаций(взято с OEIS#A238724):
def primfacs(n): i = 2 primfac = [] while i * i 1: primfac.append(n) return primfac Отслеживать
ответ дан 28 мар 2017 в 13:44
27.2k 2 2 золотых знака 45 45 серебряных знаков 76 76 бронзовых знаков
29 мар 2017 в 3:38
В коде есть два существенных момента, из-за которых он ищет все делители вместо факторизации. Добавлю ещё одно изменение ради оптимизации и получится такой код:
import math number=int(input()) for i in range(2, int(math.sqrt(number)) + 1): # обычно делитель не будет больше корня while (number % i == 0): # while, а не if print(i) number //= i # убираем множитель из числа if (number != 1): # но один делитель может быть больше корня print (number) PS: Но вообще вариант с циклом из соседнего ответа лучше.
Отслеживать
ответ дан 31 мар 2017 в 11:25
123k 24 24 золотых знака 126 126 серебряных знаков 303 303 бронзовых знака
"случай, что само число было простым" В number всегда будет последний простой делитель(кроме случая, когда на входе была единица).
31 мар 2017 в 11:49
@vp_arth, нет, во всех остальных случаях там 1. Мы же делим на каждый простой делитель до корня, пока они не кончатся.
31 мар 2017 в 11:50
ок, не всегда, иногда там 1. Однако, 51 => range(2, 8) => 3, 17!
31 мар 2017 в 12:00
@vp_arth, да, понял. Поменял комментарий. Если хочешь, можешь ещё сам поправить что-нибудь. Но код-то верный во втором варианте.
31 мар 2017 в 14:02
Посмотрите, например, как сделано здесь. Существуют более сложные и эффективные методы. А также обратите внимание на решето Эратосфена (тут). Если вы хотите получать факторизацию не для одного числа, а для большого набора числел, то выгоднее использовать перебор по простым. Об этом я расскажу чуть ниже.
Кроме того, я думаю, что Вы имели ввиду, что хотите разложить число на простые множители, ведь так? Я сужу по Вашему замечанию, насчёт правильного ответа:
7 = [63, 3, 21, 3, 7] А должно: 63 = 3 * 3 * 7 if n > 1: factors.append(n) else: break говорят о том, что Вы пытаетесь искать все делители.
В таком случае, нужно писать правильно заголовок вопроса, чтобы не смущать людей.
Насчёт Вашего решения. Я не понимаю, зачем Вы добавляете в итоговый список текущий делитель. Это неверно, так как добавлять в итоговый список следует лишь простые числа, а текущий делитель, очевидно, не простой. Так что строки:
if n > 1: factors.append(n) else: break Для того, чтобы получить все делители, вам нужно слегка модифицировать Ваш алгоритм:
#!/usr/bin/env python3 n = int(input("Integer: ")) factors = [] d = 2 m = n # Запомним исходное число while d * d = <>' .format(m, factors)) # Выводим исходное число и все простые множители. Теперь о предподсчёте с простыми числами. Легко понять, что коль скоро мы знаем все простые числа, то выгоднее не перебирать те элементы, которые являются сами по себе произведением простых. Т.е. будем перебирать только числа:
2, 3, 5, 7, 11, 13 . 4, 6, 8, 9, 10, 12 . оставим в покое, так как они являются произведением простых. Для этого, с помощью решета Эратосфена вычислим заранее все простые до некоторого предела ( 2 ^ 64 ). После этого полученное со входной строки число для факторизации будем раскладывать по простым следующим образом. Делим число n до тех пор, пока оно делится на i -ое простое. Все простые будем записывать в factors . Как только число перестаёт делиться на i -ое, берём i+1 -ое число. И так до тех пор, пока n != 1 .
Спешу заметить, что хранение простых чисел, разумеется, является затратным. НО! Для большинства задач очень подходит, так как не требуется вычислять простые числа свыше 100000000 . Оперативная память современных ПК более чем позволяет хранить 1ГБ и более данных. Простых чисел оказывается не слишком много. Согласно одной довольно известной теореме о простых числах, их оказывается порядка n/ln(n) при возрастании n . Это означает, что для 100000000 их будет примерно 5,3 млн , что является вполне себе допустимым. Более того, даже 1 млрд. чисел выдержит среднестатистический ПК, так как простых числе окажется не более 50 млн . А значит, для памяти это будет 50 млн . 4-байтовых чиселок, т.е. 200000000 байт . В мегабайтах это всего лишь 200 . Так что большой проблемы в хранении нет.
Разложение чисел на множители
Как для целого числа n перчислить все его возможные разложения на множители?
Мне приходит в голову такой алгоритм: разложить n на простые множители, затем перечислять все подмножества этого множества. Но так как в множестве 2^k подмножеств, это работает невыносимо долго, к тому же, многие разложения перечисляются многократно.
Deleted
16.02.13 18:27:51 MSK
J ★★★★
( 16.02.13 18:30:52 MSK )
вас это беспокоит, хотите поговорить об этом? 🙂
Harald ★★★★★
( 16.02.13 18:33:08 MSK )
вроде у Шнайера в прикладной криптографии описывается алгоритм. Если погуглить, тоже что-нибудь найдется
Harald ★★★★★
( 16.02.13 18:34:08 MSK )
man factor + смотри исходники
anonymous
( 16.02.13 18:42:37 MSK )
Как для целого числа n перчислить все его возможные разложения на множители?
redgremlin ★★★★★
( 16.02.13 18:54:12 MSK )
Берёшь квантовый компьютер и раскладываешь за ~logN.
Artificial_Thought ★★★★
( 16.02.13 19:47:29 MSK )
Ответ на: комментарий от redgremlin 16.02.13 18:54:12 MSK
Разложение числа на множители отличается от разложения на простые множители тем, что оно не единственно.
Deleted
( 16.02.13 19:47:35 MSK )
Ответ на: комментарий от Deleted 16.02.13 19:47:35 MSK
По ссылке сходить, конечно, слабо?
Факториза́цией натурального числа называется его разложение в произведение простых множителей
redgremlin ★★★★★
( 16.02.13 19:50:53 MSK )
tyakos ★★★
( 16.02.13 19:56:21 MSK )
Я думаю, что надо адаптировать алгоритм тот разбиения на слагаемые.
Kakadu ★
( 16.02.13 19:57:48 MSK )
Дальше сам думай.
Dragon59 ★★
( 16.02.13 20:03:08 MSK )
Наверное, всё же придётся делать разбиение множества алгоритмом бэктрекинга. Плохо то, что алгоритм экспоненциальный, значит медленный.
Deleted
( 16.02.13 20:17:47 MSK )
Ответ на: комментарий от Deleted 16.02.13 20:17:47 MSK
За 50$ поделюсь линейным, только тсс - никому.
Dragon59 ★★
( 16.02.13 20:23:03 MSK )
Ответ на: комментарий от anonymous 16.02.13 18:42:37 MSK
Меряемся писюками, у кого быстрее 🙂
$ time factor 9999999999999997111 9999999999999997111: 9999999999999997111 real 0m4.994s user 0m4.972s sys 0m0.004s anonymous
( 16.02.13 20:42:43 MSK )
Ответ на: комментарий от Dragon59 16.02.13 20:23:03 MSK
Линейный алгоритм получения всех возможных комбинаций множителей заданного числа? Он существует? О_О
TheKnight ★★★
( 16.02.13 20:45:07 MSK )
Ответ на: комментарий от anonymous 16.02.13 20:42:43 MSK
time factor 9999999999999997111 9999999999999997111: 9999999999999997111 real 0m0.043s user 0m0.002s sys 0m0.000s TheKnight ★★★
( 16.02.13 20:46:17 MSK )
Ответ на: комментарий от TheKnight 16.02.13 20:46:17 MSK
time python -c "print '9999999999999997111: 9999999999999997111'" 9999999999999997111: 9999999999999997111 real 0m0.020s user 0m0.016s sys 0m0.000sanonymous
( 16.02.13 20:58:40 MSK )
Ответ на: комментарий от TheKnight 16.02.13 20:45:07 MSK
Это сарказм? У меня плохо с детектором, так что на всякий случай выше по треду ссылка на википедию, выбирай любой.
Dragon59 ★★
( 16.02.13 21:00:41 MSK )
Ответ на: комментарий от anonymous 16.02.13 20:58:40 MSK
$ time factor 9999999999999997111 9999999999999997111: 9999999999999997111 real 0m0.002s user 0m0.000s sys 0m0.002s $ factor --version factor (GNU coreutils) 8.20 Packaged by Gentoo (8.20-r2 (p1.4)) Copyright (C) 2012 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later . This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Written by Paul Rubin, Torbjorn Granlund, and Niels Moller. quasimoto ★★★★
( 16.02.13 21:05:42 MSK )
Ответ на: комментарий от TheKnight 16.02.13 20:46:17 MSK
Поиск привёл как всегда к книге Кнута. Глава 7.2.1 «Разбиение мультимножеств».
Deleted
( 16.02.13 21:05:49 MSK )
Ответ на: комментарий от quasimoto 16.02.13 21:05:42 MSK
С таблицей значений? К слову в дебиане:
time factor 9999999999999997111 9999999999999997111: 9999999999999997111 real 0m6.517s user 0m6.464s sys 0m0.036s factor (GNU coreutils) 8.13 Copyright (C) 2011 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later . This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Written by Paul Rubin.anonymous
( 16.02.13 21:16:49 MSK )
Ответ на: комментарий от Dragon59 16.02.13 21:00:41 MSK
Кажется я несу чушь.
TheKnight ★★★
( 16.02.13 21:24:35 MSK )
Последнее исправление: TheKnight 16.02.13 21:26:50 MSK (всего исправлений: 1)
Ответ на: комментарий от anonymous 16.02.13 20:42:43 MSK
real 0m0.080s user 0m0.003s sys 0m0.002s Компу 8 лет. Что у тебя за гуано мамонта?
NorokKrin
( 16.02.13 22:06:53 MSK )
Ответ на: комментарий от NorokKrin 16.02.13 22:06:53 MSK
Говно мамонта у тебя вместо мозгов (и у меня вместо ос). Ты бы версии сравнил для начала — где-то в 2011-2012 factor-ng.c смержили в factor.c, делай выводы.
anonymous
( 16.02.13 22:09:39 MSK )
Ответ на: комментарий от anonymous 16.02.13 21:16:49 MSK
Эвристики разные, скорее всего (make-prime-list.c -> primes.h тоже). Например
$ time factor 123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789: 3 3 3 7 11 13 19 757 3607 3803 52579 70541929 14175966169 440334654777631 factor 123456789123456789123456789123456789123456789123456789 0,04s user 0,00s system 97% cpu 0,044 total $ timeout 5 factor 123456789123456789123456789123456789123456789123456 quasimoto ★★★★
( 16.02.13 22:45:22 MSK )
Ответ на: комментарий от anonymous 16.02.13 20:42:43 MSK
~$ time factor 9999999999999997111 9999999999999997111: 9999999999999997111 real 0m0.001s user 0m0.000s sys 0m0.000s ~$ factor --version factor (GNU coreutils) 8.20 Copyright (C) 2012 Free Software Foundation, Inc. wota ★★
( 16.02.13 22:48:20 MSK )
Последнее исправление: wota 16.02.13 22:49:50 MSK (всего исправлений: 1)
есть как бы основная теорема арифметики ( о единственности представления числа в виде произведения степеней простых делителей)
где a,b,c, ряд(весь) простых чисел Z,Y,X. - в какой степени (т.е максимальное число сколько раз можно последовательно делить начиная с исходного без остатка) этот простой делитель делит данное число F - очевидно что большинство показателей будет нули ( и обычно их(соот простые числа) просто не выписывают))
обрати внимания что такая запись(не нулевые показатели) похожа на позиционую запись.
можеш понять что всякие делители(включая 1 и само число) исходного числа в такой форме имеет на каждой позиции число в диапазоне от нуля до максимальной для даного числа.
т.е общее число делителей(с учётом 1 и самого числа) есть произведение степеней( увеличеных на 1) рекурсивно можно красиво перечислять все делители .
qulinxao ★★☆
( 16.02.13 23:20:49 MSK )
quasimoto ★★★★
( 16.02.13 23:49:14 MSK )
Ответ на: комментарий от Kakadu 16.02.13 19:57:48 MSK
Я думаю, что надо адаптировать алгоритм тот разбиения на слагаемые.
не подойдет, автор же явно написал:
для целого числа n перечислить все его возможные разложения на множители?
нужно адаптировать алгоритм разбиения на все возможные слагаемые
anonymous
( 17.02.13 00:09:05 MSK )
Ответ на: комментарий от qulinxao 16.02.13 23:20:49 MSK
итить, когда уже в этой теме дойдут до таблицы умножения?