Muszę rozłożyć dowolną liczbę na czynniki pierwsze. Liczba ma być wpisana do konsoli ręcznie, obsługa liczb do 2 do potęgi 31. Preferowana oszczędność pamięci, proszę o podpowiedzi, jak się do tego zabrać?
0
0
Troche to czasu może jednak zająć, gdyż pomnożyć dwie duże liczby pierwsze jest łatwo natomiast rozkład na czynniki trwa znacznie dłużej.
Możesz np. wyznaczyć liczby pierwsze (metodą sita) i zapisać je gdzieś (starczy do sqrt(2^31) ) i używając modulo dzielić sprawdzić czy sie dzieli liczba (zaczynając od 2 poprzez kolejne liczby). plusy - będzie szybciej minusy - musisz mieć gdzieś zapisane te liczby pierwsze
Możesz też dopiero po wpisaniu liczby przez użytkownika wyznaczyć liczby pierwsze od 2 do sqrt(liczba). Nie trzeba mieć zapisanych liczb ale trwa dłużej.
To tylko taki mój pomysł, poczekaj na odpowiedzi bardziej zaawansowanych informatyków :P
0
Wyznaczać sobie liczby pierwsze od 2 do sqrt(liczba)? Rozumiem, że pracujemy na superkomputerze? :| Zwykłego inta można jeszcze rozłożyć w sensownym czasie podanym przez Ciebie sposobem.