Zadanie w pythonie

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:))

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".

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:

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.

0

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


def prime_factors(number):
    result = set()
    start = _
    for __ in __ : 
        while __:
            result.add(__)
            number = __
            start = __
    if result == __:
        result =  #co i dlaczego
    return result
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:

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
0

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

n = jakaś_liczba
k = 2 #pierwszy czynnik

while ___:
    if ___:
        n =
        print(k)
    else:
        k += 1

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0