数论-yiteyi-C++库

给定一个数字n，任务是计算其初始值。原始的（表示为P _N #)是前n个素数的乘积。原始的一个数的阶乘类似于一个数的阶乘。在本原数中，并不是所有的自然数都相乘，只有素数相乘才能计算出一个数的本原数。它用P#表示。 例如：

null

Input: n = 3Output: 30 Priomorial = 2 * 3 * 5 = 30As a side note, factorial is 2 * 3 * 4 * 5Input: n = 5Output: 2310Primorial = 2 * 3 * 5 * 7 * 11

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

A. 幼稚的方法 就是逐个检查从1到n的所有数字是否为素数，如果是，则将乘法存储在结果中，同样地，将素数乘法的结果存储到n。一 有效率的 方法是使用圣代拉姆筛然后将它们相乘，计算出基本值。

C++

                         // C++ program to find Primorial of given numbers                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         const                                     int                                     MAX = 1000000;                       
           
                         // vector to store all prime less than and equal to 10^6                       
                         vector <                                     int                                     > primes;                       
           
                         // Function for sieve of sundaram. This function stores all                       
                         // prime numbers less than MAX in primes                       
                         void                                     sieveSundaram()                       
                         {                       
                                                 // In general Sieve of Sundaram, produces primes smaller                       
                                                 // than (2*x + 2) for a number given number x. Since                       
                                                 // we want primes smaller than MAX, we reduce MAX to half                       
                                                 // This array is used to separate numbers of the form                       
                                                 // i+j+2ij from others where 1 <= i <= j                       
                                                 bool                                     marked[MAX/2 + 1] = {0};                       
           
                                                 // Main logic of Sundaram. Mark all numbers which                       
                                                 // do not generate prime number by doing 2*i+1                       
                                                 for                                     (                                     int                                     i = 1; i <= (                                     sqrt                                     (MAX)-1)/2 ; i++)                       
                                                 for                                     (                                     int                                     j = (i*(i+1))<<1 ; j <= MAX/2 ; j += 2*i +1)                       
                                                 marked[j] =                                     true                                     ;                       
           
                                                 // Since 2 is a prime number                       
                                                 primes.push_back(2);                       
           
                                                 // Print other primes. Remaining primes are of the                       
                                                 // form 2*i + 1 such that marked[i] is false.                       
                                                 for                                     (                                     int                                     i=1; i<=MAX/2; i++)                       
                                                 if                                     (marked[i] ==                                     false                                     )                       
                                                 primes.push_back(2*i + 1);                       
                         }                       
           
                         // Function to calculate primorial of n                       
                         int                                     calculatePrimorial(                                     int                                     n)                       
                         {                       
                                                 // Multiply first n primes                       
                                                 int                                     result = 1;                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 result = result * primes[i];                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 5;                       
                                                 sieveSundaram();                       
                                                 for                                     (                                     int                                     i = 1 ; i<= n; i++)                       
                                                 cout <<                                     "Primorial(P#) of "                                     << i <<                                     " is "                       
                                                 << calculatePrimorial(i) <<endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find Primorial of given numbers                       
                         import                                     java.util.*;                       
           
                         class                                     GFG{                       
           
                         public                                     static                                     int                                     MAX =                                     1000000                                     ;                       
           
                         // vector to store all prime less than and equal to 10^6                       
                         static                                     ArrayList<Integer> primes =                                     new                                     ArrayList<Integer>();                       
           
                         // Function for sieve of sundaram. This function stores all                       
                         // prime numbers less than MAX in primes                       
                         static                                     void                                     sieveSundaram()                       
                         {                       
                                                 // In general Sieve of Sundaram, produces primes smaller                       
                                                 // than (2*x + 2) for a number given number x. Since                       
                                                 // we want primes smaller than MAX, we reduce MAX to half                       
                                                 // This array is used to separate numbers of the form                       
                                                 // i+j+2ij from others where 1 <= i <= j                       
                                                 boolean                                     [] marked =                                     new                                     boolean                                     [MAX];                       
           
                                                 // Main logic of Sundaram. Mark all numbers which                       
                                                 // do not generate prime number by doing 2*i+1                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= (Math.sqrt(MAX) -                                     1                                     ) /                                     2                                     ; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = (i * (i +                                     1                                     )) <<                                     1                                     ; j <= MAX /                                     2                                     ; j +=                                     2                                     * i +                                     1                                     )                       
                                                 {                       
                                                 marked[j] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Since 2 is a prime number                       
                                                 primes.add(                                     2                                     );                       
           
                                                 // Print other primes. Remaining primes are of the                       
                                                 // form 2*i + 1 such that marked[i] is false.                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= MAX /                                     2                                     ; i++)                       
                                                 {                       
                                                 if                                     (marked[i] ==                                     false                                     )                       
                                                 {                       
                                                 primes.add(                                     2                                     * i +                                     1                                     );                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Function to calculate primorial of n                       
                         static                                     int                                     calculatePrimorial(                                     int                                     n)                       
                         {                       
                                                 // Multiply first n primes                       
                                                 int                                     result =                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 result = result * primes.get(i);                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     5                                     ;                       
                                                 sieveSundaram();                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 System.out.println(                                     "Primorial(P#) of "                                     +i+                                     " is "                                     +calculatePrimorial(i));                       
                                                 }                       
                         }                       
                         }                       
                         // This Code is contributed by mits                       

Python3

                         # Python3 program to find Primorial of given numbers                       
                         import                                     math                       
                         MAX                                     =                                     1000000                                     ;                       
           
                         # vector to store all prime less than and equal to 10^6                       
                         primes                                     =                                     [];                       
           
                         # Function for sieve of sundaram. This function stores all                       
                         # prime numbers less than MAX in primes                       
                         def                                     sieveSundaram():                       
                                   
                                                 # In general Sieve of Sundaram, produces primes smaller                       
                                                 # than (2*x + 2) for a number given number x. Since                       
                                                 # we want primes smaller than MAX, we reduce MAX to half                       
                                                 # This array is used to separate numbers of the form                       
                                                 # i+j+2ij from others where 1 <= i <= j                       
                                                 marked                                     =                                     [                                     False                                     ]                                     *                                     (                                     int                                     (                                     MAX                                     /                                     2                                     )                                     +                                     1                                     );                       
           
                                                 # Main logic of Sundaram. Mark all numbers which                       
                                                 # do not generate prime number by doing 2*i+1                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,                                     int                                     ((math.sqrt(                                     MAX                                     )                                     -                                     1                                     )                                     /                                     2                                     )                                     +                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (((i                                     *                                     (i                                     +                                     1                                     ))<<                                     1                                     ),(                                     int                                     (                                     MAX                                     /                                     2                                     )                                     +                                     1                                     ),(                                     2                                     *                                     i                                     +                                     1                                     )):                       
                                                 marked[j]                                     =                                     True                                     ;                       
           
                                                 # Since 2 is a prime number                       
                                                 primes.append(                                     2                                     );                       
           
                                                 # Print other primes. Remaining primes are of the                       
                                                 # form 2*i + 1 such that marked[i] is false.                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,                                     int                                     (                                     MAX                                     /                                     2                                     )):                       
                                                 if                                     (marked[i]                                     =                                     =                                     False                                     ):                       
                                                 primes.append(                                     2                                     *                                     i                                     +                                     1                                     );                       
           
                         # Function to calculate primorial of n                       
                         def                                     calculatePrimorial(n):                       
                                                 # Multiply first n primes                       
                                                 result                                     =                                     1                                     ;                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 result                                     =                                     result                                     *                                     primes[i];                       
                                                 return                                     result;                       
           
                         # Driver code                       
                         n                                     =                                     5                                     ;                       
                         sieveSundaram();                       
                         for                                     i                                     in                                     range                                     (                                     1                                     ,n                                     +                                     1                                     ):                       
                                                 print                                     (                                     "Primorial(P#) of"                                     ,i,                                     "is"                                     ,calculatePrimorial(i));                       
           
                         # This code is contributed by mits                       

C#

                         // C# program to find Primorial of given numbers                       
                         using                                     System;                       
                         using                                     System.Collections;                       
           
                         class                                     GFG{                       
           
                         public                                     static                                     int                                     MAX = 1000000;                       
           
                         // vector to store all prime less than and equal to 10^6                       
                         static                                     ArrayList primes =                                     new                                     ArrayList();                       
           
                         // Function for sieve of sundaram. This function stores all                       
                         // prime numbers less than MAX in primes                       
                         static                                     void                                     sieveSundaram()                       
                         {                       
                                                 // In general Sieve of Sundaram, produces primes smaller                       
                                                 // than (2*x + 2) for a number given number x. Since                       
                                                 // we want primes smaller than MAX, we reduce MAX to half                       
                                                 // This array is used to separate numbers of the form                       
                                                 // i+j+2ij from others where 1 <= i <= j                       
                                                 bool                                     [] marked =                                     new                                     bool                                     [MAX];                       
           
                                                 // Main logic of Sundaram. Mark all numbers which                       
                                                 // do not generate prime number by doing 2*i+1                       
                                                 for                                     (                                     int                                     i = 1; i <= (Math.Sqrt(MAX) - 1) / 2 ; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = (i * (i + 1)) << 1 ; j <= MAX / 2 ; j += 2 * i + 1)                       
                                                 {                       
                                                 marked[j] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Since 2 is a prime number                       
                                                 primes.Add(2);                       
           
                                                 // Print other primes. Remaining primes are of the                       
                                                 // form 2*i + 1 such that marked[i] is false.                       
                                                 for                                     (                                     int                                     i = 1; i <= MAX / 2; i++)                       
                                                 {                       
                                                 if                                     (marked[i] ==                                     false                                     )                       
                                                 {                       
                                                 primes.Add(2 * i + 1);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Function to calculate primorial of n                       
                         static                                     int                                     calculatePrimorial(                                     int                                     n)                       
                         {                       
                                                 // Multiply first n primes                       
                                                 int                                     result = 1;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 result = result * (                                     int                                     )primes[i];                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 5;                       
                                                 sieveSundaram();                       
                                                 for                                     (                                     int                                     i = 1 ; i <= n; i++)                       
                                                 {                       
                                                 System.Console.WriteLine(                                     "Primorial(P#) of "                                     +i+                                     " is "                                     +calculatePrimorial(i));                       
                                                 }                       
                         }                       
                         }                       
                         // This Code is contributed by mits                       

PHP

                         <?php                       
                         // PHP program to find Primorial                       
                         // of given numbers                       
                         $MAX                                     = 100000;                       
           
                         // vector to store all prime less                       
                         // than and equal to 10^6                       
                         $primes                                     =                                     array                                     ();                       
           
                         // Function for sieve of sundaram.                       
                         // This function stores all prime                       
                         // numbers less than MAX in primes                       
                         function                                     sieveSundaram()                       
                         {                       
                                                 global                                     $MAX                                     ,                                     $primes                                     ;                       
                                   
                                                 // In general Sieve of Sundaram,                       
                                                 // produces primes smaller than                       
                                                 // (2*x + 2) for a number given                       
                                                 // number x. Since we want primes                       
                                                 // smaller than MAX, we reduce MAX                       
                                                 // to half. This array is used to                       
                                                 // separate numbers of the form                       
                                                 // i+j+2ij from others where 1 <= i <= j                       
                                                 $marked                                     =                                     array_fill                                     (0,                                     $MAX                                     / 2 + 1, 0);                       
           
                                                 // Main logic of Sundaram. Mark all numbers which                       
                                                 // do not generate prime number by doing 2*i+1                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <= (sqrt(                                     $MAX                                     ) - 1) / 2 ;                                     $i                                     ++)                       
                                                 for                                     (                                     $j                                     = (                                     $i                                     * (                                     $i                                     + 1)) << 1 ;                       
                                                 $j                                     <=                                     $MAX                                     / 2 ;                                     $j                                     += 2 *                                     $i                                     + 1)                       
                                                 $marked                                     [                                     $j                                     ] = true;                       
           
                                                 // Since 2 is a prime number                       
                                                 array_push                                     (                                     $primes                                     , 2);                       
           
                                                 // Print other primes. Remaining primes                       
                                                 // are of the form 2*i + 1 such that                       
                                                 // marked[i] is false.                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $MAX                                     / 2;                                     $i                                     ++)                       
                                                 if                                     (                                     $marked                                     [                                     $i                                     ] == false)                       
                                                 array_push                                     (                                     $primes                                     , (2 *                                     $i                                     + 1));                       
                         }                       
           
                         // Function to calculate primorial of n                       
                         function                                     calculatePrimorial(                                     $n                                     )                       
                         {                       
                                                 global                                     $primes                                     ;                       
                                   
                                                 // Multiply first n primes                       
                                                 $result                                     = 1;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $result                                     =                                     $result                                     *                                     $primes                                     [                                     $i                                     ];                       
                                                 return                                     $result                                     ;                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 5;                       
                         sieveSundaram();                       
                         for                                     (                                     $i                                     = 1 ;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     "Primorial(P#) of "                                     .                                     $i                                     .                       
                                                 " is "                                     . calculatePrimorial(                                     $i                                     ) .                                     ""                                     ;                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find Primorial                       
                         // of given numbers                       
                         let MAX = 100000;                       
           
                         // vector to store all prime less                       
                         // than and equal to 10^6                       
                         let primes =                                     new                                     Array();                       
           
                         // Function for sieve of sundaram.                       
                         // This function stores all prime                       
                         // numbers less than MAX in primes                       
                         function                                     sieveSundaram()                       
                         {                       
                                   
                                                 // In general Sieve of Sundaram,                       
                                                 // produces primes smaller than                       
                                                 // (2*x + 2) for a number given                       
                                                 // number x. Since we want primes                       
                                                 // smaller than MAX, we reduce MAX                       
                                                 // to half. This array is used to                       
                                                 // separate numbers of the form                       
                                                 // i+j+2ij from others where 1 <= i <= j                       
                                                 let marked =                                     new                                     Array(MAX / 2 + 1).fill(0);                       
           
                                                 // Main logic of Sundaram. Mark all numbers which                       
                                                 // do not generate prime number by doing 2*i+1                       
                                                 for                                     (let i = 1; i <= (Math.sqrt(MAX) - 1) / 2 ; i++)                       
                                                 for                                     (let j = (i * (i + 1)) << 1 ;                       
                                                 j <= MAX / 2 ; j += 2 * i + 1)                       
                                                 marked[j] =                                     true                                     ;                       
           
                                                 // Since 2 is a prime number                       
                                                 primes.push(2);                       
           
                                                 // Print other primes. Remaining primes                       
                                                 // are of the form 2*i + 1 such that                       
                                                 // marked[i] is false.                       
                                                 for                                     (let i = 1; i <= MAX / 2; i++)                       
                                                 if                                     (marked[i] ==                                     false                                     )                       
                                                 primes.push(2 * i + 1);                       
                         }                       
           
                         // Function to calculate primorial of n                       
                         function                                     calculatePrimorial(n)                       
                         {                       
                                                 // Multiply first n primes                       
                                                 let result = 1;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 result = result * primes[i];                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         let n = 5;                       
                         sieveSundaram();                       
                         for                                     (let i = 1 ; i<= n; i++)                       
                                                 document.write(                                     "Primorial(P#) of "                                     + i +                                     " is "                                     +                       
                                                 calculatePrimorial(i) +                                     "<br>"                                     );                       
           
                         // This code is contributed by gfgking                       
           
                         </script>                       

输出：

Primorial(P#) of 1 is 2Primorial(P#) of 2 is 6Primorial(P#) of 3 is 30Primorial(P#) of 4 is 210Primorial(P#) of 5 is 2310

本文由 萨希尔·查布拉（杀手） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章