Zadanie c++


(Random_guy) #1

Witam mam problem z tym zadaniem. Czy mógłby ktoś napisać taki program ?
Napisz funkcję rozkładającą liczbę n>1 na czynniki pierwsze. Np dla liczby 24 podanej jako parametr, powinien pojawić się następujący rozkład: 24=2 2 2 3


(kuba3351) #2

Napisać można, ale zasadniczo nie praktykuje się tutaj odrabiania za kogoś pracy domowej od początku do końca. Najpierw spróbuj sam, jak się nie uda, to pomożemy.


(bachus) #3

Nawet nie spróbowałeś wpisać w google - to przecież jedno z podstaowych zadań programistycznych.


(kowgli) #4

Na pewno są szybsze sposoby, ale wersja “brute force” jako od razu przychodzi do głowy to znalezienie wszystkich liczb pierwszych <= n / 2, a następnie próba dzielenia bez reszty zaczynając od najmniejszej. Po podzieleniu wyliczamy nowe n i kontynuujemy dzielenie od najmniejszej pierwszej <= n/2. Kończymy kiedy n = 1.

Np. dla n = 15
Znajdujemy liczby pierwsze 2, 3, 5, 7

Czy dzieli się przez 2? Nie
Czy dzieli się przez 3? Tak … Wypisujemy ‘3’, n = 15/3 = 5
Czy dzieli się przez 3? Nie
Czy dzieli się przez 5? Tak … Wypisujemy ‘5’, n = 5/5= 1
Koniec

‘++’ w C++ jest tu oczywiście do niczego nie potrzebne. W zadaniu nie ma nic obiektowego.

Podpowiedź - “czy a dzieli się bez reszty przez b” w językach C-pochodnych pisze się “if(a % b == 0) { … }”

Prostą optymalizacją byłoby nie wyliczanie wszystkich liczb pierwszych na początku. Tylko szukanie kolejnej dopiero kiedy będzie potrzebna.


(krystian3w) #5

http://cpp0x.pl/kursy/Kurs-C++/Poziom-1/Operacje-matematyczne/13