Как в питоне разложить число на множители

разложите число n на простые множители в порядке вырастания

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

Дано натуральное число n. Совершите разложение числа n на простые
множители в порядку вырастания. Результат выведите в один
рядок.
Используйте цикл while
если понадобиться (if,else,elif,end)
Пример:
24
Результат:
2 2 2 3

Лучшие ответы ( 1 )

Здесь вы можете заказать любую студенческую или школьную работу.

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Разложите данное натуральное число N на простые множители
Разложите данное натуральное число N на простые множители.

Разложите натуральное число N на простые множители и определите наибольший множитель произведения
Задача№1 Разложите натуральное число N на простые множители и определите наибольший множитель.

Разложить число на простые множители в порядке возрастания
Помогите что нужно поменять? Условия задачи: Лимит времени 2000 мс. Лимит памяти 65000 Кб. .

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

Разложить целое число N на простые множители и вывести результат в порядке возрастания
Требуется разложить целое число N на простые множители и вывести результат в порядке возрастания. .

Status 418

Эксперт Python

4569 / 2337 / 601
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3

Лучший ответ

Сообщение было отмечено tima228 как решение

Решение

1 2 3 4 5 6 7

n = int(input()) i = 2 while n > 1: while n % i == 0: print(i, end=' ') n //= i i += 1

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Разложить целое число N на простые множители и вывести результат в порядке возрастания множителей
Требуется разложить целое число N на простые множители и вывести результат в порядке возрастания.

Разложите число на множители N с помощью процедуры с параметром
я просто решила эту задачу, а вот как написать благодаря процедуры с параметром? var n,i: Integer;.

Процедуры и функции. Разложить заданное целое число на простые множители. Множители сохранить в массиве
Pascal. Разложить заданное целое число на простые множители. Множители сохранить в массиве. Решить.

Или воспользуйтесь поиском по форуму:

Программа разложения числа на простые множители в Python

В этом руководстве мы обсудим, как получить простой множитель данного числа с помощью программы разложения числа в Python. Все мы знакомы с простыми числами – это числа, которые можно разделить на единицу или на себя. Например – 1, 2, 3, 5, 7, 11, 13, ……

Нахождение всех простых множителей числа

Если пользователь вводит число как 12, то на выходе должно быть 2, 2, 3, а если на входе 315 – выход должен быть «3 3 5 7». Программа должна вернуть все простые множители данного числа. Простые множители 330 – это 2, 3, 5 и 11. Следовательно, 11 является наиболее значимым простым множителем 330.

Например: 330 = 2 × 3 × 5 × 11.

Прежде чем писать программу на Python, давайте разберемся со следующими догадками.

1-я гипотеза – может быть хотя бы один простой множитель, который будет меньше √n в случае, если n не является простым числом.

Доказательство. Существуют два больших числа sqrt(n), их произведение также должно делить n, но оно будет превышать n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).

Давайте посмотрим на следующий шаг, чтобы выполнить такую операцию.

p or q

2-я гипотеза – может быть более 1 простого множителя n больше, чем sqrt(n).

Доказательство. Предположим, что есть два больших числа sqrt(n), тогда их произведение также должно делить n, но оно будет больше n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).

Давайте посмотрим на следующий шаг, чтобы выполнить такую операцию.

Пример – программа Python для печати простых множителей.

import math # Below function will print the # all prime factor of given number def prime_factors(num): # Using the while loop, we will print the number of two's that divide n while num % 2 == 0: print(2,) num = num / 2 for i in range(3, int(math.sqrt(num)) + 1, 2): # while i divides n , print i ad divide n while num % i == 0: print(i,) num = num / i if num > 2: print(num) # calling function num = 200 prime_factors(num)

2 2 2 5 5

В приведенном выше коде мы импортировали математический модуль. Функция prime_factor() отвечает за печать составного числа. Сначала мы получаем четные числа; после этого все оставшиеся простые множители должны быть нечетными. В цикле for число должно быть нечетным, поэтому мы увеличили i на два. Цикл for будет вычислять квадратный корень n раз.

Давайте разберемся в следующем свойстве составных чисел.

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

Программа будет работать следующим образом:

На первом шаге найдем наименьший простой множитель i.
Вхождение i будет удалено из n путем многократного деления n на i.
Повторим оба вышеуказанных шага для деления n и i = i + 2. Оба шага будут повторяться до тех пор, пока n не станет либо 1, либо простым числом.

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

Пример – 2: Программа Python для определения наибольшего простого множителя заданного числа.

def largest_prime_factor(n): i = 2 while i * i

Представить натуральное число в виде простых сомножителей

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

Чтобы найти все простые сомножители натурального числа, надо его пробовать делить на простые числа, начиная с 2. Если заданное число делится без остатка, значит его делитель — это число, которое входит в состав сомножителей, из которых формируется заданное число. Как только такой сомножитель будет найден, заданное число следует на него разделить, т.е. получить новое заданное число и уже к нему заново подбирать простой делитель. Например, дано число 24. Первое натуральное число, на которое оно делится, — это 2. Значит 2 — это первый простой сомножитель. В результате деления получается 12. Далее снова находим, что 12 делится на 2. Далее 6 делится на 2. Далее 3 делится на 3. Таким образом получаем: 24 = 2 * 2 * 2 * 3.

Поскольку список простых чисел заранее неизвестен, то можно подбирать делители, увеличивая каждый следующий на 1, а не искать простые числа. Ведь если число не делится на 2, то оно не разделится и на 4, 6 и т.д.

В программах ниже есть решения с использованием оператора goto и без него. С ним решение получается короче, но с точки зрения современного программирования его использование нежелательно.

Алгоритм сводится к следующему. Пока заданное число не будет сведено к 1, делить его на натуральные числа от 2 и т.д. Как только деление будет произведено без остатка, то значит был найден простой сомножитель. Он выводится на экран, заданное число на него делится и снова начинается поиск простого делителя, начиная с 2.

Pascal

 
label again; 
var n, i: word; 
begin 
readln(n); 
again: 
while n > 1 do begin 
i := 2; 
while True do 
if n mod i = 0 then begin 
n := n div i; 
write(i,' '); 
goto again; 
end 
else i := i + 1; 
end; 
writeln; 
end.

Язык Си

 
#include  
main() unsigned int n, i; 
scanf("%d", &n); 
again: 
while (n > 1) i = 2; 
while (1) if (n%i == 0) n = n / i; 
printf("%d ", i); 
goto again; 
> 
else i += 1; 
> 
> 
printf("\n"); 
>

 
 
3636 
2 2 3 3 101

Python

разложение на простые множители python

 
n = int(input()) 
while n > 1: 
i = 2 
f = 0 
while 1: 
if n%i == 0: 
n = n // i 
print(i, end=' ') 
f = 1 
break 
else: 
i += 1 
if f == 1: 
continue 
print()

КуМир

 
алг простые сомножители 
нач 
цел ч, п, ф 
ввод ч 
ф := 1 
нц пока ч > 1 
нц пока да 
если ф = 1 то 
п := 2 
ф := 0 
все 
если mod(ч,п) = 0 то 
ч := div(ч,п) 
вывод п, " " 
ф := 1 
выход 
иначе 
п := п + 1 
все 
кц 
кц 
кон

 
 
96 
2 2 2 2 2 3

Basic-256

 
input n 
again: 
while n > 1 
i = 2 
while 1 
if n%i = 0 then 
n = n \ i 
print i + " "; 
gosub again 
endif 
i = i+1 
endwhile 
endwhile

 
 
1024 
2 2 2 2 2 2 2 2 2 2

Разложение чисел на множители

Как для целого числа 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.000s

anonymous
( 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

итить, когда уже в этой теме дойдут до таблицы умножения?