NWD metodą "poprzez rozkład na czynniki pierwsze"

0

Hej.
Dostałem zadanie domowe na napisanie programu największy wspólny dzielnik metodą "poprzez rozkład na czynniki pierwsze". Wszystko byłoby dobrze jak miałbym to zrobić metodą euklidesa. Ale nie mam pojęcia jak zabrać się za metodę przez rozkład na czynniki pierwsze. Tym bardziej że muszę użyć do tego obiektów klasy ArrayList do pamiętania listy czynników pierwszych.:(
Bardzo bym prosił o pomoc w napisaniu. Pewnie za dużo wymagam. Ale nie mam innej możliwości.
Z góry dziękuje

0

A wiesz jak to się na kartce robi? No, to w Javie tak samo, tylko zapiszesz to jako pętlę.

0

Wiem jak to się robi na kartce. Gorzej jest to zapisać w javie. Tym bardziej jak muszę użyć obiekty klasy ArrayList. Nie mam pojęcia jak obliczyć i potem przypisać do listy. I co dalej. Mam porównać dwie stworzone listy, żeby znaleźć te same czynniki. Naprawdę nie wiem jak się za to zabrać...

0

Założyłem, że algorytm ma szukać NWD dwóch liczb, nie zastanawiałem sie nad wydajnością.

  1. wczytaj liczby n,k
  2. wyznacz liczby pierwsze z przedziału [2, Math.sqrt(Math.max(n,k))], możesz je pamiętać w tablicy primes
  3. utwórz trzy (puste na razie) obiekty typu ArrayList factors_n, factors_k i factors
for(int i=0;i<primes.length;i++)
{
    while((n % primes[i])==0)
    {
         factors_n.add(primes[i]);
         //coś jeszcze trzeba zrobić
    }
}
  1. analogicznie dla liczby k
  2. pętla po factors_n, przy pomocy indexOf() sprawdzasz czy liczba jest w factors_k, jeśli jest, to dopisujesz do factors i usuwasz z factors_k
    Nie sprawdzałem.

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