Java, szukanie NWD :: 4programmers.net

Rejestracja:ponad 12 lat
Ostatnio:ponad 11 lat
Postów:7

witam udało mi się napisac program który wyznacza wspólny dzielnik dwóch liczb:

Kopiuj

import java.util.Scanner; 

public class NWD { 
         public static void main(String[] args) { 
                 System.out.print("Podaj liczbę: "); 
                 Scanner sc = new Scanner(System.in); 
                 long z1  = sc.nextLong(); 
                 System.out.print("Podaj nastepną liczbę: "); 
                 long z2 = sc.nextLong(); 
                 sc.close(); 
                 while (z1 != z2) { 
                         if (z1 < z2) 
                             z2-=z1; 
                         else 
                             z1-=z2; 
                 } 
                 System.out.println("NWD liczb wynosi " + z1); 
         } 
}

teraz chodzi mi o to zeby powstało coś takiego jak w zadaniu:
2520 jest najmniejszą liczbą, która może być podzielona bez reszty przez każdą z liczb od 1 do 10. Jaka jest najmniejsza całkowita liczba dodatnia, która może być podzielona bez reszty przez każdą z liczb z zakresu 1 .. 20 ?

msm 2013-01-18 21:26

Powiedz mi, po co nazwałeś wątek JAVA DZIELENIE LICZB POMOC!!!? Nadawaj chociaż /trochę/ opisowe tematy.

hfaua

2013-01-18 22:41

hfaua2013-01-18 22:41

Rejestracja:ponad 12 lat
Ostatnio:ponad 6 lat
Postów:17

Według mnie, obliczanie NWD na niewiele Ci się przyda w tym zadaniu. Przydadzą Ci się raczej informacje na temat liczb złożonych oraz faktoryzacji. Należy zauważyć, że poszukiwana liczba musi zawierać w swoim rozkładzie wszystkie liczby pierwsze (w odpowiednich potęgach), które występują w rozkładach liczb od 1 do 20. Szybkie rozwiązanie:

Tworzysz tablicę liczb całkowitych o 20 elementach i zerujesz ją.
Faktoryzujesz każdą z liczb od 1 do 20
2. 1. Jeśli dana liczba pierwsza wystąpiła w wyższej potędze niż jest to zapisane w tablicy, to aktualizujemy tablicę wykładnikiem naszej liczby pierwszej
2. 2. W przeciwnym wypadku nie następuje aktualizacja
Wynik otrzymujemy mnożąc liczby pierwsze tyle razy, ile wskazuje pole w tablicy

Przykład w C:

Kopiuj

// Tablica z wykładnikami
int exponents[20];

// Zerowanie tablicy
for(int i = 0; i < 20; i++)
  exponents[i] = 0;
 
for(int i = 1; i <= 20; i++)
{
   // Faktoryzowana liczba
   int number = i;
   // Liczba, pierwsza którą rozkładamy `number`
   int divisior = 2;
   // Liczba wystąpień danej liczby pierwszej w rozkładzie liczby `number`
   int count = 0;
 
   while(number > 1)
   {
       // `divisior` występuje w rozkładzie `number`
       if(number % divisior == 0)
      {
          number = number / divisior;
          count++;
			  
          if(count > exponents[divisior])
              exponents[divisior] = count;
      }
      // `divisior` nie występuje w rozkładzie `number`
      else
      {
          divisior++;
          count = 0;
      }
   }
}
 
int result = 1;

// Mnożenie liczb
for(int i = 0; i < 20; i++)
	for(int j = 0; j < exponents[i]; j++)
		result = result * i;
		
printf("%d\n", result);