Zadanie w pythonie

Zadanie w pythonie
SP
  • Rejestracja:ponad 6 lat
  • Ostatnio:ponad 6 lat
  • Postów:2
0

Witam, dopiero zaczynam z pythonem i mam takie zadanie do wykonania, mógłby ktoś pomóc lub wytłumaczyć?
Zadanie:
Napisz program, który dokona rozkładu liczby n na czynniki pierwsze (wyświetli wszystkie dzielniki tej liczby będące liczbami pierwszymi).
Rozpoczynamy od k=2 - jest to najmniejsza liczba pierwsza. Jeśli rozkładana liczba n dzieli się przez k=2, to wyświetlamy:
2
i skracamy naszą liczbę n przez k=2.
Czynność powtarzamy tak długo, jak długo liczba n jest podzielna przez 2.
W kolejnym kroku szukamy następnego dzielnika rozkładanej liczby. Będzie to następna liczba pierwsza, czyli k=3. Czynność powtarzamy tak długo, jak długo liczba n jest podzielna przez k=3.
W kolejnych krokach zwiększamy k o 1 i sprawdzamy podzielność, pamiętając o skracaniu liczby n przez k. Czynności te powtarzamy do momentu uzyskania wartości n=1.

Byłbym naprawdę wdzięczny za pomoc:))

SE
  • Rejestracja:prawie 8 lat
  • Ostatnio:ponad 3 lata
  • Postów:318
0

Tak konkretnie, to w którym momencie pisania tego kodu masz problem? Nie wspominając już o tym, że zawsze możesz wpisać w google "Python prime factors".

lion137
  • Rejestracja:około 8 lat
  • Ostatnio:39 minut
  • Postów:4935
0

Jak duże liczby to ma faktoryzować? Załóżmy, że ta njawiększa liczba to N. Wygeneruj sobie tablicę kolejnych liczb pierwszych o wielkości pierwiastek z N. I teraz faktoryzacja, primes to wyżej wymieniona lista liczb pierwszych, zachęcam do rozwiązania tego samemu:

Kopiuj
def factors(n, primes):
    output = set()
    for __ in __:
        while __:
            output.add(__)
            __
        if __:
            break
    return output

Tam gdzie są podkreślenia trzeba wstawić kawałek kodu:)

EDIT: Lista liczb pierwszych musi być większa: do połowy N. Do pierwiastka wystarczyłoby, żeby znaleźć jakiś dzielnik.


edytowany 2x, ostatnio: lion137
enedil
Bzdury. Do pierwiastka starczy. Bo jeśli n=km gdzie k< m, to aby znaleźć jakiś dzielnik m wystarczy mieć listę liczb pierwszych mniejszych niż sqrt(m) < sqrt(n), więc w szczególności pierwsza uzyskana lista wystarczy.
enedil
O, znowu Monsieur Daję Odpowiedzi z Subtelnymi Błędami, a Krytykę Ignoruję, teraz ogarnąłem że to także Ty
lion137
Zeby znalezc co najmniej jeden dzielnik wystarczy; ale nie wystarczy, zeby tak prosto znalezc wszystkie faktory. Przyklad: 86 = 2 * 43. Rozwiazaniem, zeby nie komplikowac bylby, np. Nieskonczony generator.
SI
Albo po znalezieniu pierwszej od razu zacząć dzielić. Wtedy wygenerujemy ich dokładnie tyle ile trzeba.
enedil
@lion137: napisałem właśnie dlaczego wystarczy
SE
  • Rejestracja:prawie 8 lat
  • Ostatnio:ponad 3 lata
  • Postów:318
0

Wersja z jednym parametrem(mało wydajna, zwłaszcza przy dużych liczbach):

Kopiuj

def prime_factors(number):
    result = set()
    start = _
    for __ in __ : 
        while __:
            result.add(__)
            number = __
            start = __
    if result == __:
        result =  #co i dlaczego
    return result
edytowany 9x, ostatnio: Serechiel
lion137
  • Rejestracja:około 8 lat
  • Ostatnio:39 minut
  • Postów:4935
0

Wydaje się, najprostsze rozwiązanie, skoro dla dowolnie dużej liczby i tak będziemy musieli wdepnąć w trial division, to można od razu robić z generatorem:

Kopiuj
import math
def is_prime(n):
    """Naiwne is_prime"""
    if n == 1: return False
    elif n == 2 or n == 3:
        return True
    else:
        for i in range(5, int(math.sqrt(n)) + 1 , 2):
            if n % i == 0:
                return False
        return True

def primes_gen():
    """Infinite primes generator"""
    i = 2
    while True:
        if is_prime(i):
            yield i
        i += 1

def factors(n):
    primes = primes_gen()    
    output = set()
    for p in primes:
        while n % p == 0:
            output.add(p)
            n //= p
        if n <= 1:
            break
    return output

SE
  • Rejestracja:prawie 8 lat
  • Ostatnio:ponad 3 lata
  • Postów:318
0

Podejrzewam, że na tym etapie chodzi o coś bardziej topornego. Coś w tym stylu:

Kopiuj
n = jakaś_liczba
k = 2 #pierwszy czynnik

while ___:
    if ___:
        n =
        print(k)
    else:
        k += 1
SP
Tak, o to chodzilo. Zrobilem jiz to zadanie wczoraj. Dziekuje za odpowiedz:)

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.