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:

1. zaczynamy od listy liczb od $1$ do $k$,
2. wykreślamy liczby postaci $i + j + 2ij$, dla $0 < i, j \leq k$,
3. niewykreślone liczby mnożymy razy dwa,
4. do wyników dodajemy jeden.

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. zaczynamy od listy liczb od $0$ do $k = \left\lfloor \frac{N-2}{2}\right\rfloor$,
2. wykreślamy liczby postaci $i + j + 2ij$, dla $0 < i, j \leq k$,
3. niewykreślone liczby mnożymy razy dwa,
4. do wyników dodajemy jeden,
5. pierwszą liczbę zastępujemy dwójką.

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:

1. zastanów się, czy kolejność zmiennych $i$ oraz $j$ ma znaczenie?
2. zastanów się, jak może się zmieniać $j$ przy ustalonym $i$, aby liczba postaci $i+j+2ij \leq k$ (czyli aby znajdowała się na liście)?
3. zastanów się, czy $i$ oraz $j$ mogą być dowolnie duże, na przykład bliskie $k$, aby wciąż $i+j+2ij \leq k$?

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).