Liczby Gładkie

Definicja

Liczby gładka jest nazywana K-gładką jeśli wszystkie jej dzielniki pierwsze są nie większe niż K i należy do zbioru liczb naturalnych.

Przykłady

W przypadku sprawdzania stopnia K gładkości wybranej liczby a można rozłożyć liczbę na czynniki pierwszą. Szukany stopień K to oczywiście największa liczba w rozkładzie. Na tej podstawie można wywnioskować, że stopień K liczby gładkiej jest zawsze liczbą pierwszą. W tabelce zostały przedstawione przykładowe liczby oraz wyliczony ich stopień:

Implementacja

Do implementacji przyda się znajomość na temat liczb pierwszych. Liczb pierwszych dzielących dana liczbę a należy szukać w zakresie [2, a/2]. W celu uniknięcia sprawdzania czy liczba, którą chcemy dzielić jest pierwsza warto usunąć wszystkie wielokrotności poprzedni znalezionej liczby pierwszej tj. najpierw dzielić liczbę przez 2 dopóki jest możliwe, potem 3, 3 itd. Jeśli nie zostanie znaleziona żadna liczba w zakresie, która dzieli a to K = a.

1. int podajStopienGladkosci(int a){
2.   int a_kopia = a;
3.   for(int i = 2; i <= a/2; i++){
4.     while(a_kopia % i == 0)
5.       a_kopia /= i;
6.     if(a_kopia == 1)
7.       return i;
8.   }
9.   return a;
10. }

(1.) Program przyjmuje liczbę naturalną a, a wynikiem działania funkcji będzie stopień gładkości K. (2.) Utworzenie kopii liczby a, którą będzie można modyfikować. (3.) Dla każdej liczby z zakresu [2, a/2] (4.) o ile liczba i dzieli a_kopia to (5.) dzieli liczbę a_kopia przez i. (6.) Jeśli po dzieleniu a_kopia wynosi jeden to znaczy, że rozkład został zakończony, a (7.) największą dzielącą liczbą pierwszą jest i. (9.) Jeśli pętla zostanie zakończona, ale nie zostanie znaleziony żaden dzielnik to znaczy, że liczba jest pierwsza, dlatego należy wtedy zwrócić wartość a.

Testowanie funkcji

Najprostszy program, który wczyta od użytkownika liczbę i wypisze na ekran K-gładkość wygląda tak:

1. int main () {
2.   int a;
3.   cin >> a;
4.   cout << podajStopienGladkosci(a) << endl;
5.   system("pause");
6.   return 0;
7. }

• Kod źródłowy Implementacja

Zadania

n pierwszych liczb stopnia K

Jeśli wypisać kolejny liczby K-gładkie można zauważyć, że wszystkie są wielokrotnościami liczby K. Jednak z tego zbioru wypadają liczby, które są postaci Kq, gdzie q to liczba pierwsza większa od K.

Zadanie 1

1. Na podstawie powyższej notatki napisz program, który wczyta od użytkownika dwie liczby naturalne K i n. Program powinien wypisać pierwsze n liczb o stopniu gładkości K bez wykorzystania funkcji sprawdzającej stopień gładkości liczby.

Przykładowo dla danych:

1. 5 10

program powinien wypisać:

1. 7 14 21 28 35 42 49 56 63 70

• Kod źródłowy Zadanie 1