рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рдХрд░рддрд╛ рд╣реИ
рдпрд╣ рдЯреВрд▓ рдЖрдкрдХреЛ рдмрддрд╛рддрд╛ рд╣реИ рдХрд┐ рдХреЛрдИ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рдЕрднрд╛рдЬреНрдп (prime) рд╣реИ рдпрд╛ рднрд╛рдЬреНрдп (composite)ред 1 рд╕реЗ рдмрдбрд╝реА рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдареАрдХ рджреЛ рд╣реА рднрд╛рдЬрдХ рд╣реЛрддреЗ рд╣реИрдВ тАФ 1 рдФрд░ рд╕реНрд╡рдпрдВ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ред рд╡рд╣реАрдВ рднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рдХрдо рд╕реЗ рдХрдо рдПрдХ рдЕрддрд┐рд░рд┐рдХреНрдд рднрд╛рдЬрдХ рд╣реЛрддрд╛ рд╣реИред 0 рдФрд░ 1 рди рдЕрднрд╛рдЬреНрдп рд╣реИрдВ рдФрд░ рди рд╣реА рднрд╛рдЬреНрдп, рдЗрд╕рд▓рд┐рдП рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдореЗрдВ 2 рдпрд╛ рдЙрд╕рд╕реЗ рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛ рджрд░реНрдЬ рдХрд░реЗрдВред
рдЗрд╕рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
рдмреЙрдХреНрд╕ рдореЗрдВ рдХреЛрдИ рднреА рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рд▓рд┐рдЦреЗрдВ рдФрд░ рд╕рдмрдорд┐рдЯ рдХрд░реЗрдВред рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдмрддрд╛ рджреЗрдЧрд╛ рдХрд┐ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ рдХрд┐рд╕ рд╢реНрд░реЗрдгреА рдореЗрдВ рдЖрддреА рд╣реИред рдЕрдЧрд░ рд╕рдВрдЦреНрдпрд╛ рднрд╛рдЬреНрдп рд╣реБрдИ, рддреЛ рдпрд╣ рдЙрд╕рдХрд╛ рд╕рдмрд╕реЗ рдЫреЛрдЯрд╛ рдЕрднрд╛рдЬреНрдп рдЧреБрдгрдирдЦрдВрдб рдФрд░ рдПрдХ рдЙрджрд╛рд╣рд░рдг рдЧреБрдгрдирдЦрдВрдбрди рднреА рджрд┐рдЦрд╛рдПрдЧрд╛ (рд╕рдмрд╕реЗ рдЫреЛрдЯрд╛ рдЧреБрдгрдирдЦрдВрдб \(\times\) рдЙрд╕рд╕реЗ рдореЗрд▓ рдЦрд╛рддрд╛ рд╕рд╣-рдЧреБрдгрдирдЦрдВрдб)ред
рд╕реВрддреНрд░ рдХреЛ рд╕рдордЭреЗрдВ
рдпрд╣ рдЬрд╛рдБрдЪ рднрд╛рдЧ-рдкрд░реАрдХреНрд╖рдг (trial division) рдкрд░ рдЖрдзрд╛рд░рд┐рдд рд╣реИред рдпрд╣ рдкрддрд╛ рдХрд░рдиреЗ рдХреЗ рд▓рд┐рдП рдХрд┐ n рднрд╛рдЬреНрдп рд╣реИ рдпрд╛ рдирд╣реАрдВ, рдЖрдкрдХреЛ рдХреЗрд╡рд▓ 2 рд╕реЗ рд▓реЗрдХрд░ n рдХреЗ рд╡рд░реНрдЧрдореВрд▓ рддрдХ рдХреЗ рднрд╛рдЬрдХ d рд╣реА рдЬрд╛рдБрдЪрдиреЗ рд╣реЛрддреЗ рд╣реИрдВред рдЕрдЧрд░ рдРрд╕рд╛ рдХреЛрдИ d n рдХреЛ рдмрд┐рдирд╛ рд╢реЗрд╖ рдХреЗ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░ рджреЗ, рддреЛ n рднрд╛рдЬреНрдп рд╣реИред рдЕрдЧрд░ рдХреЛрдИ рднреА рди рдХрд░реЗ, рддреЛ n рдЕрднрд╛рдЬреНрдп рд╣реИред рдХреЗрд╡рд▓ \(\sqrt{n}\) рддрдХ рдЬрд╛рдБрдЪрдирд╛ рдЗрд╕рд▓рд┐рдП рдХрд╛рдо рдХрд░рддрд╛ рд╣реИ рдХреНрдпреЛрдВрдХрд┐ рдЕрдЧрд░ \(n = a \times b\) рд╣реЛ, рддреЛ рджреЛрдиреЛрдВ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдореЗрдВ рд╕реЗ рдХрдо рд╕реЗ рдХрдо рдПрдХ \(\le \sqrt{n}\) рдЬрд╝рд░реВрд░ рд╣реЛрдЧрд╛ред
$$\text{Prime if } n > 1 \text{ and } \nexists\, d \in [2, \lfloor\sqrt{n}\rfloor] : n \bmod d = 0$$
$$\begin{gathered} \text{Classify}(n) = \begin{cases} \text{Prime} & \nexists\, d \in [2,\lfloor\sqrt{n}\rfloor],\; n \bmod d = 0 \\[0.4em] \text{Composite} & \exists\, d \in [2,\lfloor\sqrt{n}\rfloor],\; n \bmod d = 0 \\[0.4em] \text{Neither} & n < 2 \end{cases} \end{gathered}$$
рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг
рдорд╛рди рд▓реАрдЬрд┐рдП \(n = 91\)ред 91 рдХрд╛ рд╡рд░реНрдЧрдореВрд▓ рд▓рдЧрднрдЧ 9.54 рд╣реИ, рдЗрд╕рд▓рд┐рдП рд╣рдо 2, 3, 5, 7, 9 рдХреА рдЬрд╛рдБрдЪ рдХрд░рддреЗ рд╣реИрдВред рд╣рдореЗрдВ рдорд┐рд▓рддрд╛ рд╣реИ рдХрд┐ \(91 \div 7 = 13\) рдкреВрд░рд╛-рдкреВрд░рд╛ рдмрдБрдЯ рдЬрд╛рддрд╛ рд╣реИ, рдпрд╛рдиреА 91 рднрд╛рдЬреНрдп рд╣реИ рдЬрд┐рд╕рдХрд╛ рд╕рдмрд╕реЗ рдЫреЛрдЯрд╛ рдЧреБрдгрдирдЦрдВрдб 7 рд╣реИ рдФрд░ рдЧреБрдгрдирдЦрдВрдбрди \(7 \times 13\) рд╣реИред рдЗрд╕рдХреЗ рд╡рд┐рдкрд░реАрдд, 97 рдХрд╛ 9 рддрдХ рдХреЛрдИ рднрд╛рдЬрдХ рдирд╣реАрдВ рдорд┐рд▓рддрд╛, рдЗрд╕рд▓рд┐рдП рд╡рд╣ рдЕрднрд╛рдЬреНрдп рд╣реИред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓
рдХреНрдпрд╛ 1 рдЕрднрд╛рдЬреНрдп рд╣реИ? рдирд╣реАрдВред рдкрд░рд┐рднрд╛рд╖рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдареАрдХ рджреЛ рдЕрд▓рдЧ-рдЕрд▓рдЧ рдзрдирд╛рддреНрдордХ рднрд╛рдЬрдХ рд╣реЛрдиреЗ рдЪрд╛рд╣рд┐рдП, рдЬрдмрдХрд┐ 1 рдХрд╛ рдХреЗрд╡рд▓ рдПрдХ рд╣реА рднрд╛рдЬрдХ рд╣реИред
рдХреНрдпрд╛ 2 рдЕрднрд╛рдЬреНрдп рд╣реИ? рд╣рд╛рдБред рдпрд╣ рдПрдХрдорд╛рддреНрд░ рд╕рдо (even) рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ рд╣реИред
рд╡рд░реНрдЧрдореВрд▓ рдкрд░ рд╣реА рдЬрд╛рдБрдЪ рдХреНрдпреЛрдВ рд░реЛрдХ рджреЗрддреЗ рд╣реИрдВ? \(\sqrt{n}\) рд╕реЗ рдмрдбрд╝рд╛ рдХреЛрдИ рднреА рдЧреБрдгрдирдЦрдВрдб \(\sqrt{n}\) рд╕реЗ рдЫреЛрдЯреЗ рдХрд┐рд╕реА рдЧреБрдгрдирдЦрдВрдб рдХреЗ рд╕рд╛рде рдЬреЛрдбрд╝рд╛ рд╣реБрдЖ рд╣реЛрддрд╛ рд╣реИ, рдЬрд┐рд╕реЗ рдЦреЛрдЬ рдкрд╣рд▓реЗ рд╣реА рдЬрд╛рдБрдЪ рдЪреБрдХреА рд╣реЛрддреА рд╣реИред рдЗрд╕рд▓рд┐рдП \(\sqrt{n}\) рд╕реЗ рдЖрдЧреЗ рдЬрд╛рдБрдЪрдирд╛ рдмреЗрдХрд╛рд░ рд╣реИред