素性测试|第1组（介绍和学校方法）-yiteyi-C++库

给定一个正整数，检查该数字是否为素数。素数是一个大于1的自然数，除1和它本身外，没有其他正因子。前几个素数的例子是{2,3,5， 例如：

null

Input:  n = 11Output: trueInput:  n = 15Output: falseInput:  n = 1Output: false

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

学校方法 一个简单的解决方案是迭代从2到n-1的所有数字，并对每个数字检查它是否除以n。如果我们找到任何除以的数字，我们将返回false。下面是这个方法的实现。

C++

                         // A school method based C++ program to check if a                       
                         // number is prime                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         bool                                     isPrime(                                     int                                     n)                       
                         {                       
                                                 // Corner case                       
                                                 if                                     (n <= 1)                                     return                                     false                                     ;                       
           
                                                 // Check from 2 to n-1                       
                                                 for                                     (                                     int                                     i=2; i<n; i++)                       
                                                 if                                     (n%i == 0)                       
                                                 return                                     false                                     ;                       
           
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver Program to test above function                       
                         int                                     main()                       
                         {                       
                                                 isPrime(11)?  cout <<                                     " true"                                     : cout <<                                     " false"                                     ;                       
                                                 isPrime(15)?  cout <<                                     " true"                                     : cout <<                                     " false"                                     ;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A school method based JAVA program                       
                         // to check if a number is prime                       
                         class                                     GFG {                       
                                   
                                                 static                                     boolean                                     isPrime(                                     int                                     n)                       
                                                 {                       
                                                 // Corner case                       
                                                 if                                     (n <=                                     1                                     )                                     return                                     false                                     ;                       
                                   
                                                 // Check from 2 to n-1                       
                                                 for                                     (                                     int                                     i =                                     2                                     ; i < n; i++)                       
                                                 if                                     (n % i ==                                     0                                     )                       
                                                 return                                     false                                     ;                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 // Driver Program                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 if                                     (isPrime(                                     11                                     ))                       
                                                 System.out.println(                                     " true"                                     );                       
                                                 else                       
                                                 System.out.println(                                     " false"                                     );                       
                                                 if                                     (isPrime(                                     15                                     ))                       
                                                 System.out.println(                                     " true"                                     );                       
                                                 else                       
                                                 System.out.println(                                     " false"                                     );                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by Nikita Tiwari.                       

Python3

                         # A school method based Python3                       
                         # program to check if a number                       
                         # is prime                       
           
                         def                                     isPrime(n):                       
           
                                                 # Corner case                       
                                                 if                                     n <                                     =                                     1                                     :                       
                                                 return                                     False                       
           
                                                 # Check from 2 to n-1                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n):                       
                                                 if                                     n                                     %                                     i                                     =                                     =                                     0                                     :                       
                                                 return                                     False                                     ;                       
           
                                                 return                                     True                       
           
                         # Driver Program to test above function                       
                         print                                     (                                     "true"                                     )                                     if                                     isPrime(                                     11                                     )                                     else                                     print                                     (                                     "false"                                     )                       
                         print                                     (                                     "true"                                     )                                     if                                     isPrime(                                     14                                     )                                     else                                     print                                     (                                     "false"                                     )                       
           
                         # This code is contributed by Smitha Dinesh Semwal                       

C#

                         // A optimized school method based C#                       
                         // program to check if a number is prime                       
                         using                                     System;                       
           
                         namespace                                     prime                       
                         {                       
                                                 public                                     class                                     GFG                       
                                                 {                       
                                                 public                                     static                                     bool                                     isprime(                                     int                                     n)                       
                                                 {                       
                                                 // Corner cases                       
                                                 if                                     (n <= 1)                                     return                                     false                                     ;                       
                                   
                                                 for                                     (                                     int                                     i = 2; i < n; i++)                       
                                                 if                                     (n % i == 0)                       
                                                 return                                     false                                     ;                       
                                   
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 if                                     (isprime(11)) Console.WriteLine(                                     "true"                                     );                       
                                                 else                                     Console.WriteLine(                                     "false"                                     );                       
                                   
                                                 if                                     (isprime(15)) Console.WriteLine(                                     "true"                                     );                       
                                                 else                                     Console.WriteLine(                                     "false"                                     );                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // A school method based PHP                       
                         // program to check if a number                       
                         // is prime                       
           
                         function                                     isPrime(                                     $n                                     )                       
                         {                       
                                                 // Corner case                       
                                                 if                                     (                                     $n                                     <= 1)                                     return                                     false;                       
           
                                                 // Check from 2 to n-1                       
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 if                                     (                                     $n                                     %                                     $i                                     == 0)                       
                                                 return                                     false;                       
           
                                                 return                                     true;                       
                         }                       
           
                         // Driver Code                       
                         $tet                                     = isPrime(11) ?                                     " true"                                     :                       
                                                 " false"                                     ;                       
                         echo                                     $tet                                     ;                       
                         $tet                                     = isPrime(15) ?                                     " true"                                     :                       
                                                 " false"                                     ;                       
                         echo                                     $tet                                     ;                       
           
                         // This code is contributed by m_kit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // A school method based Javascript program to check if a                       
                         // number is prime                       
                         function                                     isPrime(n)                       
                         {                       
                                                 // Corner case                       
                                                 if                                     (n <= 1)                                     return                                     false                                     ;                       
           
                                                 // Check from 2 to n-1                       
                                                 for                                     (let i = 2; i < n; i++)                       
                                                 if                                     (n % i == 0)                       
                                                 return                                     false                                     ;                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver Program to test above function                       
                                                 isPrime(11)? document.write(                                     " true"                                     +                                     "<br>"                                     ): document.write(                                     " false"                                     +                                     "<br>"                                     );                       
                                                 isPrime(15)? document.write(                                     " true"                                     +                                     "<br>"                                     ): document.write(                                     " false"                                     +                                     "<br>"                                     );                       
           
                         // This code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出：

truefalse

该解的时间复杂度为O（n） 优化的学校方法 我们可以进行以下优化：

我们不必查到n，我们可以查到n√n，因为n的较大因子必须是已经检查过的较小因子的倍数。
通过观察所有素数的形式为6k±1（2和3除外），可以进一步改进算法。这是因为对于某些整数k和i=-1、0、1、2、3或4，所有整数都可以表示为（6k+i）；2分（6k+0）、（6k+2）、（6k+4）；3分（6k+3）。所以一个更有效的方法是测试n是否可以被2或3整除，然后检查表6k±1中的所有数字。（来源：维基百科 )

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章