Napisz program szukający liczb doskonałych mniejszych od $N$. Przetestuj go dla $N=100$.
Napisz program liczący ile jest par liczb zaprzyjaźnionych mniejszych od $N$. Przetestuj go dla $N=10000$.
Zaimplementujemy sito Sundarama, które jest alternatywnym sposobem generowania listy liczb pierwszych. Główny pomysł przebiega następująco:
Efektem są liczby pierwsze większe od $2$ i mniejsze od $2k+2$. Następujący wariant wygeneruje wszystkie liczby pierwsze mniejsze od $N$:
1) Napisz funkcję sito_Sundarama(N), która wygeneruje liczby pierwsze mniejsze od $N$. Wyniki porównaj z wynikami uzyskanymi za pomocą sita Eratostenesa z wykładu.
2) Do podstawowego algorytmu spróbuj dodać optymalizację, na przykład:
Wybierz i uzasadnij poprawność jednej dowolnie wybranej optymalizacji (z listy powyżej lub innej). Zaimplementuj ją jako funkcję sito_Sundarama2. Wyniki porównaj z wynikami uzyskanymi za pomocą sita Eratostenesa z wykładu.
3) Porównaj czas działania trzech algorytmów do generowania listy liczb pierwszych: jednego wariantu sita Eratostenesa, podstawowej wersji sita Sundarama (z podpunktu 1) oraz zoptymalizowanej przez siebie wersji sita Sundarama (z podpunktu 2).