苏菲·日尔曼首相-yiteyi-C++库

编写一个程序，以不到n.a.的价格打印所有Sophie Germain号码质数 P 被称为 索菲素数 如果 2p+1 也是一个质数。号码 2p+1 被称为 安全素数 例如 11 是一个素数，11*2+1=23也是一个素数，所以，11是索菲·杰曼的素数。前几位苏菲·德文素数是2、3、5、11、23、29、41、53、83、89、113、131、173、179…

null

例如：

Input : 25Output : 2 3 5 11 23

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

下面是将Sophie Germain的数字打印到n以下的程序。解决办法很简单。为了得到n以下的所有Sophie数，我们将循环到n，对于循环中的每个数，我们可以检查数字和 （2*数字+1） 都是 首要的 或者没有，为了检查这一点，我们使用了埃拉托斯坦筛方法

下面是这种方法的实现。

C++

                         // CPP program to print all sophie german                       
                         // prime number till n.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to detect prime number                       
                         // here we have used sieve method                       
                         //                           https://www.geeksforgeeks.org/sieve-of-eratosthenes/                                    
                         // to detect prime number                       
                         bool                                     sieve(                                     int                                     n,                                     bool                                     prime[])                       
                         {                       
                                                 for                                     (                                     int                                     p = 2; p * p <= n; p++) {                       
           
                                                 // If prime[p] is not changed, then                       
                                                 // it is a prime                       
                                                 if                                     (prime[p] ==                                     true                                     ) {                       
           
                                                 // Update all multiples of p                       
                                                 for                                     (                                     int                                     i = p * 2; i <= n; i += p)                       
                                                 prime[i] =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         void                                     printSophieGermanNumber(                                     int                                     n)                       
                         {                       
                                                 // We have made array till 2*n +1                       
                                                 // so that we can check prime number                       
                                                 // till that and conclude about sophie                       
                                                 // german prime .                       
                                                 bool                                     prime[2 * n + 1];                       
                                                 memset                                     (prime,                                     true                                     ,                                     sizeof                                     (prime));                       
                                                 sieve(2 * n + 1, prime);                       
           
                                                 for                                     (                                     int                                     i = 2; i <= n; ++i) {                       
           
                                                 // checking every i whether it is                       
                                                 // sophie german prime or not.                       
                                                 if                                     (prime[i] && prime[2 * i + 1])                       
                                                 cout << i <<                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     n = 25;                       
                                                 printSophieGermanNumber(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print all                       
                         // sophie german prime number till n.                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                                   
                         class                                     GFG {                       
                                   
                                                 // function to detect prime number                       
                                                 // here we have used sieve method                       
                                                 //                           https://www.geeksforgeeks.org/sieve-of-eratosthenes/                                    
                                                 // to detect prime number                       
                                                 static                                     void                                     sieve(                                     int                                     n,                                     boolean                                     prime[])                       
                                                 {                       
                                                 for                                     (                                     int                                     p =                                     2                                     ; p * p <= n; p++) {                       
                                   
                                                 // If prime[p] is not changed, then                       
                                                 // it is a prime                       
                                                 if                                     (prime[p] ==                                     true                                     ) {                       
                                   
                                                 // Update all multiples of p                       
                                                 for                                     (                                     int                                     i = p *                                     2                                     ; i < n; i += p)                       
                                                 prime[i] =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 static                                     void                                     printSophieGermanNumber(                                     int                                     n)                       
                                                 {                       
                                                 // We have made array till 2*n +1                       
                                                 // so that we can check prime number                       
                                                 // till that and conclude about sophie                       
                                                 // german prime .                       
                                                 boolean                                     prime[]=                                     new                                     boolean                                     [                                     2                                     * n +                                     1                                     ];                       
                                                 Arrays.fill(prime,                                     true                                     );                       
                                                 sieve(                                     2                                     * n +                                     1                                     , prime);                       
                                   
                                                 for                                     (                                     int                                     i =                                     2                                     ; i < n; ++i) {                       
                                   
                                                 // checking every i whether it is                       
                                                 // sophie german prime or not.                       
                                                 if                                     (prime[i] && prime[                                     2                                     * i +                                     1                                     ])                       
                                                 System.out.print( i +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     n =                                     25                                     ;                       
                                                 printSophieGermanNumber(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by Nikita Tiwari.                       

Python3

                         # Python 3 program to print all sophie                       
                         # german prime number till n.                       
           
                         # Function to detect prime number                       
                         # here we have used sieve method                       
                         #                           https://www.geeksforgeeks.org/sieve-of-eratosthenes/                                    
                         # to detect prime number                       
                         def                                     sieve(n, prime) :                       
                                                 p                                     =                                     2                       
                                                 while                                     ( p                                     *                                     p <                                     =                                     n ):                       
                                                 # If prime[p] is not changed,                       
                                                 # then it is a prime                       
                                                 if                                     (prime[p]                                     =                                     =                                     True                                     ) :                       
                                   
                                                 # Update all multiples of p                       
                                                 for                                     i                                     in                                     range                                     (p                                     *                                     2                                     , n, p) :                       
                                                 prime[i]                                     =                                     False                       
                                   
                                                 p                                     +                                     =                                     1                       
                                   
                                   
                         def                                     printSophieGermanNumber(n) :                       
                                                 # We have made array till 2*n +1                       
                                                 # so that we can check prime number                       
                                                 # till that and conclude about sophie                       
                                                 # german prime .                       
                                                 prime                                     =                                     [                                     True                                     ]                                     *                                     (                                     2                                     *                                     n                                     +                                     1                                     )                       
                                   
                                                 sieve(                                     2                                     *                                     n                                     +                                     1                                     , prime)                       
           
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n                                     +                                     1                                     ) :                       
                                   
                                                 # checking every i whether it is                       
                                                 # sophie german prime or not.                       
                                                 if                                     (prime[i]                                     and                                     prime[                                     2                                     *                                     i                                     +                                     1                                     ]) :                       
                                                 print                                     ( i , end                                     =                                     " "                                     )                       
                                   
           
                         # Driver Code                       
                         n                                     =                                     25                       
                         printSophieGermanNumber(n)                       
           
           
                         # This code is contributed by Nikita Tiwari.                       

C#

                         // C# program to print                       
                         // all sophie german                       
                         // prime number till n.                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
                                   
                                                 // function to detect prime                       
                                                 // number here we have used                       
                                                 // sieve method                       
                                                 //                           https://www.geeksforgeeks.org/sieve-of-eratosthenes/                                    
                                                 // to detect prime number                       
                                                 static                                     void                                     sieve(                                     int                                     n,                       
                                                 bool                                     []prime)                       
                                                 {                       
                                                 for                                     (                                     int                                     p = 2;                       
                                                 p * p <= n; p++)                       
                                                 {                       
                                   
                                                 // If prime[p] is                       
                                                 // not changed, then                       
                                                 // it is a prime                       
                                                 if                                     (prime[p] ==                                     true                                     )                       
                                                 {                       
                                   
                                                 // Update all multiples of p                       
                                                 for                                     (                                     int                                     i = p * 2;                       
                                                 i < n; i += p)                       
                                                 prime[i] =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 static                                     void                                     printSophieGermanNumber(                                     int                                     n)                       
                                                 {                       
                                                 // We have made array till                       
                                                 // 2*n +1 so that we can                       
                                                 // check prime number till                       
                                                 // that and conclude about                       
                                                 // sophie german prime .                       
                                                 bool                                     []prime =                                     new                                     bool                                     [2 * n + 1];                       
                                                 for                                     (                                     int                                     i = 0;                       
                                                 i < prime.Length; i++)                       
                                                 {                       
                                                 prime[i] =                                     true                                     ;                       
                                                 }                       
                                                 sieve(2 * n + 1, prime);                       
                                   
                                                 for                                     (                                     int                                     i = 2; i < n; ++i)                       
                                                 {                       
                                   
                                                 // checking every i whether                       
                                                 // it is sophie german prime                       
                                                 // or not.                       
                                                 if                                     (prime[i] && prime[2 * i + 1])                       
                                                 Console.Write( i +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 25;                       
                                                 printSophieGermanNumber(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       

PHP

                         <?php                       
                         // PHP program to print                       
                         // all sophie german                       
                         // prime number till n.                       
           
                         // function to detect prime                       
                         // number here we have used                       
                         // sieve method                       
                         //                           https://www.geeksforgeeks.org/sieve-of-eratosthenes/                                    
                         // to detect prime number                       
                         function                                     sieve(                                     $n                                     , &                                     $prime                                     )                       
                         {                       
                                                 for                                     (                                     $p                                     = 2;                       
                                                 $p                                     *                                     $p                                     <=                                     $n                                     ;                                     $p                                     ++)                       
                                                 {                       
           
                                                 // If prime[p] is                       
                                                 // not changed, then                       
                                                 // it is a prime                       
                                                 if                                     (                                     $prime                                     [                                     $p                                     ] == true)                       
                                                 {                       
           
                                                 // Update all                       
                                                 // multiples of p                       
                                                 for                                     (                                     $i                                     =                                     $p                                     * 2;                       
                                                 $i                                     <=                                     $n                                     ;                                     $i                                     +=                                     $p                                     )                       
                                                 $prime                                     [                                     $i                                     ] = false;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         function                                     printSophieGermanNumber(                                     $n                                     )                       
                         {                       
                                                 // We have made array till                       
                                                 // 2*n +1 so that we can                       
                                                 // check prime number till                       
                                                 // that and conclude about                       
                                                 // sophie german prime .                       
                                                 $prime                                     =                                     array                                     ();                       
                                                 for                                     (                                     $i                                     = 0;                       
                                                 $i                                     < (2 *                                     $n                                     + 1);                                     $i                                     ++)                       
                                                 $prime                                     [                                     $i                                     ] = true;                       
           
                                                 sieve(2 *                                     $n                                     + 1,                                     $prime                                     );                       
           
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $n                                     ; ++                                     $i                                     )                       
                                                 {                       
           
                                                 // checking every i                       
                                                 // whether it is sophie                       
                                                 // german prime or not.                       
                                                 if                                     (                                     $prime                                     [                                     $i                                     ] &&                       
                                                 $prime                                     [2 *                                     $i                                     + 1])                       
                                                 echo                                     (                                     $i                                     .                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 25;                       
                         printSophieGermanNumber(                                     $n                                     );                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to print                       
                         // all sophie german                       
                         // prime number till n.                       
           
                         // function to detect prime                       
                         // number here we have used                       
                         // sieve method                       
                         //                           https://www.geeksforgeeks.org/sieve-of-eratosthenes/                                    
                         // to detect prime number                       
                         function                                     sieve(n, prime)                       
                         {                       
                                                 for                                     (let p = 2; p * p <= n; p++)                       
                                                 {                       
           
                                                 // If prime[p] is                       
                                                 // not changed, then                       
                                                 // it is a prime                       
                                                 if                                     (prime[p] ==                                     true                                     )                       
                                                 {                       
           
                                                 // Update all                       
                                                 // multiples of p                       
                                                 for                                     (let i = p * 2;                       
                                                 i <= n; i += p)                       
                                                 prime[i] =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         function                                     printSophieGermanNumber(n)                       
                         {                       
                                                 // We have made array till                       
                                                 // 2*n +1 so that we can                       
                                                 // check prime number till                       
                                                 // that and conclude about                       
                                                 // sophie german prime .                       
                                                 let prime =                                     new                                     Array();                       
                                                 for                                     (let i = 0; i < (2 * n + 1); i++)                       
                                                 prime[i] =                                     true                                     ;                       
           
                                                 sieve(2 * n + 1, prime);                       
           
                                                 for                                     (let i = 2; i <= n; ++i)                       
                                                 {                       
           
                                                 // checking every i                       
                                                 // whether it is sophie                       
                                                 // german prime or not.                       
                                                 if                                     (prime[i] &&                       
                                                 prime[2 * i + 1])                       
                                                 document.write(i +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         let n = 25;                       
                         printSophieGermanNumber(n);                       
           
                         // This code is contributed by                       
                         // gfgking                       
                         </script>                       

输出：

2 3 5 11 23

Sophie素数的应用：

1.它用于 密码学 随着安全素数成为密码的要素 RSA密码系统 . 2.在AKS素性测试的第一个版本中，它用于降低最坏情况的复杂性。 3.用于生成伪随机数 .

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

THE END

技术文章