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

Odpowiedz Nowy wątek
2011-09-21 22:41
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

Pozostało 580 znaków

2011-09-21 23:00
Rev
0

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


Pozostało 580 znaków

2011-09-21 23:21
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ć...

Pozostało 580 znaków

2011-09-22 08:11
bo
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
  4. for(int i=0;i<primes.length;i++)
    {
    while((n % primes[i])==0)
    {
         factors_n.add(primes[i]);
         //coś jeszcze trzeba zrobić
    }
    }
  5. analogicznie dla liczby k
  6. 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.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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