找到给定长度的复合数范围-yiteyi-C++库

给定一个整数n，我们需要找到一个正整数的范围，使得该范围内的所有数字都是复合的，且该范围的长度为n。如果有多个答案，您可以打印任何范围。复合数是一个正整数，它至少有一个除1之外的除数和自身（来源：维基 )

null

例如：

Input : 3Output : [122, 124]Explanation 122, 123, 124 are all composite numbers

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

解决方案有点棘手。因为有很多可能的答案，我们在这里讨论一个广义解。

Let the length of range be n and range starts from a then, a, a+1, a+2, ...., a+n-1 all should be composite. So the problem boils down to findingsuch 'a'.If we closely observe p! (where p is a positive integers) then we will find that, p! has factors of2, 3, 4, ..., p-1,Hence if we add i to p! such that 1 < i < p,then p! + i has a factor i, so p! + i must be composite. So we end up finding p! + 2, p! + 3, .... p! + p-1 are all composite and continuous integers forming a range [p! + 2, p! + p-1]The above range consists of p-2 elements.For a range of n elements we need to consider (n+2)!If we take a = (n+2)! + 2, Then, a + 1 = (n+2)! + 3Then, a + 2 = (n+2)! + 4...Then, a + n-1 = (n+2)! + n+1Hence,a = (n+2)! + 2 = 2*3*....*(n+2) + 2a has 2 as its divisor because (n+2)! and 2 both divides 2a + 1 = 2*3*....*(n+2) + 3a + 1 has 3 as its divisor because (n+2)! and 3 both divides 3...a + n-1 = 2*3*....*(n+2) + n+1a + n-1 has n+1 as its divisor because (n+2)! and n+1 both divides n+1Therefore range will be [ (n+2)! + 2, ( (n+2)! + 2 ) + n-1]

上述算法的示例

n = 3Then a = (n+2)! + 2a = 5! + 2a + 1 = 5! + 3a + 2 = 5! + 4Here a is divisible by 2Here a + 1 is divisible by 3Here a + 2 is divisible by 4Hence a, a+1, a+2 are all composites

C++

                         // C++ program to find a range of                       
                         // composite numbers of given length                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // method to find factorial                       
                         // of given number                       
                         int                                     factorial (                                     int                                     n)                       
                         {                       
                                                 if                                     (n == 0)                       
                                                 return                                     1;                       
           
                                                 return                                     n * factorial(n-1);                       
                         }                       
           
                         // to print range of length n                       
                         // having all composite integers                       
                         int                                     printRange(                                     int                                     n)                       
                         {                       
                         int                                     a = factorial(n + 2) + 2;                       
                         int                                     b = a + n - 1;                       
                         cout <<                                     "["                                     << a <<                                     ", "                                     << b <<                                     "]"                                     ;                       
                         return                                     0;                       
                         }                       
           
                         // Driver method                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 3 ;                       
                                                 printRange(n);                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by Anshika Goyal                       

JAVA

                         // Java program to find a range of composite                       
                         // numbers of given length                       
           
                         class                                     Test                       
                         {                       
                                                 // method to find factorial of given number                       
                                                 static                                     int                                     factorial(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n ==                                     0                                     )                       
                                                 return                                     1                                     ;                       
                                   
                                                 return                                     n*factorial(n-                                     1                                     );                       
                                                 }                       
                                   
                                                 // to print range of length n                       
                                                 //  having all composite integers                       
                                                 static                                     void                                     printRange(                                     int                                     n)                       
                                                 {                       
                                                 int                                     a = factorial(n +                                     2                                     ) +                                     2                                     ;                       
                                                 int                                     b = a + n -                                     1                                     ;                       
                                                 System.out.println(                                     "["                                     + a +                                     ", "                                     + b +                                     "]"                                     );                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                                     throws                                     Exception                       
                                                 {                       
                                                 int                                     n =                                     3                                     ;                       
                                                 printRange(n);                       
                                                 }                       
                         }                       

Python3

                         # Python program to find a range of composite                       
                         # numbers of given length                       
           
                         # function to calculate factorial                       
                         def                                     factorial(n):                       
                                                 a                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , n                                     +                                     1                                     ):                       
                                                 a                                     *                                     =                                     i                       
                                                 return                                     a                       
           
                         # to print range of length n                       
                         # having all composite integers                       
                         def                                     printRange(n):                       
                                                 a                                     =                                     factorial(n                                     +                                     2                                     )                                     +                                     2                       
                                                 b                                     =                                     a                                     +                                     n                                     -                                     1                       
                                                 print                                     (                                     "["                                     +                                     str                                     (a)                                     +                                     ", "                                     +                                     str                                     (b)                                     +                                     "]"                                     )                       
           
                         # driver code to test above functions                       
                         n                                     =                                     3                       
                         printRange(n)                       

C#

                         // C# program to find a range of                       
                         // composite numbers of given                       
                         // length                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // method to find factorial                       
                                                 // of given number                       
                                                 static                                     int                                     factorial(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n == 0)                       
                                                 return                                     1;                       
                                   
                                                 return                                     n*factorial(n-1);                       
                                                 }                       
                                   
                                                 // to print range of length n                       
                                                 // having all composite integers                       
                                                 static                                     void                                     printRange(                                     int                                     n)                       
                                                 {                       
                                                 int                                     a = factorial(n + 2) + 2;                       
                                                 int                                     b = a + n - 1;                       
                                                 Console.WriteLine(                                     "["                                     + a +                       
                                                 ", "                                     + b +                                     "]"                                     );                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 3 ;                       
                                                 printRange(n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by anuj_67.                       

PHP

                         <?php                       
                         // PHP program to find a range of                       
                         // composite numbers of given length                       
           
                         // method to find factorial                       
                         // of given number                       
                         function                                     factorial (                                     $n                                     )                       
                         {                       
                                                 if                                     (                                     $n                                     == 0)                       
                                                 return                                     1;                       
           
                                                 return                                     $n                                     * factorial(                                     $n                                     - 1);                       
                         }                       
           
                         // to print range of length n                       
                         // having all composite integers                       
                         function                                     printRange(                                     $n                                     )                       
                         {                       
                         $a                                     = factorial(                                     $n                                     + 2) + 2;                       
                         $b                                     =                                     $a                                     +                                     $n                                     - 1;                       
                         echo                                     "["                                     ,                                     $a                                     ,                                     ", "                                     ,                                     $b                                     ,                                     "]"                                     ;                       
                         return                                     0;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 3 ;                       
                         printRange(                                     $n                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                                   
                         // Javascript program to find a range of                       
                         // composite numbers of given length                       
           
                         // Method to find factorial                       
                         // of given number                       
                         function                                     factorial(n)                       
                         {                       
                                                 if                                     (n == 0)                       
                                                 return                                     1;                       
           
                                                 return                                     n * factorial(n - 1);                       
                         }                       
           
                         // To print range of length n                       
                         // having all composite integers                       
                         function                                     printRange(n)                       
                         {                       
                                                 let a = factorial(n + 2) + 2;                       
                                                 let b = a + n - 1;                       
                                   
                                                 document.write(`[${a}, ${b}]`);                       
                                   
                                                 return                                     0;                       
                         }                       
           
                         // Driver Code                       
                         let n = 3;                       
           
                         printRange(n);                       
           
                         // This code is contributed by _saurabh_jaiswal.                       
           
                         </script>                       

输出：

[122, 124]

对上述算法的分析 时间复杂度：O（n）辅助空间：O（1）

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

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

THE END

技术文章