Kolejnym liczbom pierwszym możemy przypisać ich numery, czyli kolejne dodatnie liczby naturalne. Wówczas 2 otrzyma numer 1, 3 numer 2, 5 numer 3, 7 numer 4, 11 numer 5, itd.
Każda liczba naturalna większa od jedności, która nie dzieli się przez żadną liczbę pierwszą mniejszą od niej samej, jest liczbą pierwszą. Na przykład 13 jest liczbą pierwszą gdyż nie dzieli się przez 2, 3, 5, 7 i 11.
Sprawdzanie podzielności liczby naturalnej k przez kolejne liczby pierwsze można skrócić do wartości pierwiastka z liczby k, czyli dla liczby 13 wystarczy sprawdzić podzielność przez liczby 2 i 3, ponieważ sqrt(13)=3.60555....
Algorytm generujący kolejne liczby pierwsze w oparciu o powyższą własność polega na wpisaniu do tablicy liczb 2 i 3, i na ich podstawie sprawdzeniu czy liczba 5 jest pierwsza, dopisaniu liczby 5 do tablicy, sprawdzeniu liczby 7, dopisaniu liczby 7 do tablicy, sprawdzeniu liczby 9, sprawdzeniu liczby 11, dopisaniu jej do tablicy, itd.
Niech p(k) będzie największą liczbą pierwszą, przez którą badamy podzielność liczby k, czyli p(5)=2, p(11)=3, p(21)=3, p(50)=2, p(47)=5.
Napisz program, który dla podanej liczby naturalnej n
wyznaczy
Pierwszy wiersz wejścia zawiera jedna liczbę całkowitą n
z zakresu
Pierwszy wiersz wyjścia powinien zawierać
W wierszu drugim podaj sumę p(5)+p(7)+p(11)+...+p(m), gdzie m jest liczbą pierwszą z wiersza pierwszego.
Dla danych podanych na wejściu:
10
Poprawną odpowiedzią jest wyjście:
29 24
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath Limit czasu : 0.5 s Limit pamięci : 32 MB Słowa niedozwolone :