arytmetyka modularna

Piąty rok istnienia bloga świstak.codes trzeba zacząć z przytupem. Czas więc poeksplorować temat matematyczny, który jest na pewno bliski sercom programistów lubującym się w wyzwaniach algorytmicznych typu Advent of Code. A jest to chińskie twierdzenie o resztach. Dowiedzmy się, o co w nim chodzi, jak działa i jakie ma praktyczne zastosowania. Co najważniejsze dla programistów, pokażę także, jak je zaimplementować w kodzie.

Wiemy już: czym są liczby pierwsze, jak sprawdzać, czy liczba jest pierwsza, jak w najprostszy sposób znajdować je, a także poznaliśmy teorię stojącą za znajdowaniem dużych liczb pierwszych. Przejdźmy zatem do praktyki. Czas napisać algorytm, który w krótkim czasie pozwoli nam znaleźć bardzo duże liczby pierwsze, tak jak to się robi w codziennych zastosowaniach.