����� �� �����.

������ ���������.

����������: ������ �����: ���������� �� ���������.

������� �������.

     ������, ��� ������� � ����� ������� ��������, ���������� ����� �������, ������� ����� �������� �������. � � ����� ����, ����������� ��� ����� ��������� ������������ ���������� ������������ ���� ������ �� ��������� ������� B, ����� ������ ����� ��������.

�������� ������� ������ - ������ ������ �� ��� ����� ������ �� ����� �� N. ���� �� ������ ������ ��� - ������ ����� �� ������ ;-)

     ����� �� ����� �������� N �� ��� ������� ����� �� ����� �� N. ��� ����� �� ����� ����� ��� �� ����� � ����� ������������ ���������� ������� ������� ������� �����. ���� ��� �� ���, ��, ��������, �� ����� ������ N �� ����� d � �������� ������� ���������������, ��������, 1 � 5 �� ������ 6, ��� 1,7,11,13,17,19,23,29 �� ������ 30. ����� �� ��������� ����� ������������� ������� (�� ��������� �����), ������ ��������� ��������� ������. ����� �������, ����� ��������� ��������� ��������:


������� �������.

     �����������, ��� � ��� ��� ���� ������� ������� �����: p[1] = 2, p[2] = 3, ... , p[k], ��� k > 3, ������ t := [6,4,2,4,2,4,6,2], � ������ j, ����� ��� ���� p[k] mod 30 ����� 1,7,11,13,17,19,23 ��� 29, �� j := 0,1,2,3,4,5,6 ��� 7 ��������������.
     ������� ��������� ������� ����� B, ����� ��� B >= p[k], ����� �� ������� �� ���� �������� ������� ����� �������.

     ������� �� ����� ������������� ����� ����� N, ���� �������� �������� ��������� ��� �� ���������, �, ���� ��� �� ����������, �� N - ����� ��� ������� ���������, ������� ���� ������ B.
  1. [�������������]
         ���� N <= 5, ������� ���������� 1 = 1, 2 = 2, 3 = 3, 4 = 22, 5 = 5 � ����������� �� N � �����. �����, i := -1, m := 0, L := [ N1/2 ]

  2. [C�������� �������]
         ����� m := m + 1. ���� m > k, �� i : = j - 1 � ���� � ���� 5, ����� d : = p[m].

  3. [������� �������]
         ����� r : = N mod d. ���� r = 0, �� ������� d ��� ������������� �������� N � ����� ( ��� N := N / d, L : = [ N1/2 ] � ��������� ��� 3, ���� �� ����� ���������� ���������� ��������� N).

  4. [�������?]
         ���� d >= L, �� � ������ N > 1 ������� ���������, ��� ���������� ����� N - ������� � �����. �����, ���� i < 0 ���� �� ��� 2.

  5. [��������� ��������]
         ����� i := i + 1 mod 8, d := d + t[i]. ���� d > B, �� ������� ��������� � ���, ��� ���������� ������� �������� N ������ B, ����� ���� �� ��� 3.
     �������, ��� i = -1 ���� �� ���������� ���� ������� ������� � i >= 0 ���� ���. ���� ���� �� ������� ������������ ��� ������ ������������, ����� ��� �������, ����� N - ����� ��������� ( ��������, N < 108), ��� ��� ��� ����� ���� ������ ������. ������, � ������ �������, �� ������ ������� ��� �������� ����� ����������.


������� � ������������ ����������.

     �����������, ��� �� ���������� ������� ������� �� 500'000 ( 41'538 ������� ����� ). ������� ������� ��� ����� ����������� ������� �� �������� ������ ���������� ������ �� ����������� �����������. ������ ������� ����� ������ �������� ����� �������� (��� �� ��������), � �� ���� �����, ��� ��� p[k] - p[k-1] ����� ��������� � 1 ���� ������ �������, ���� p[k] <= 1'872'851'947 ( � �������� ���� �������� - ���� p[k] <= 1'999'066'711'391).

     ����� ����, �� ����� ������ ������ ������� ����� ����, ��� �������� ������� �������, ��� ��� ���� ������ ������ ��� �������� ����� ���������.

     �, �������, �������, ��� ��� ������������� � ���������� L := [ N1/2 ] �� ����� �������������, ��� ��� �������� d >= L � ���� 4 ����� ���� �������� �� q <= L, ��� q - ��������� ������� ��� ������� N �� d : N = q * d + r, ������ ����������� ������������ � �������� � ���� 3.


����� �� ��������, � ���������� � ���������.
SpyLOG