找到一个给定长度的合成数范围
原文:https://www . geesforgeks . org/find-range-composite-numbers-给定长度/
给定一个整数 n,我们需要找到一个正整数的范围,使得该范围内的所有数字都是复合的,并且该范围的长度是 n。在多个答案的情况下,您可以打印任何范围。一个复合数是一个正整数,它至少有一个除数而不是 1 和它自己(来源: wiki )
示例:
Input : 3
Output : [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 finding
such 'a'.
If we closely observe p! (where p is a positive
integers) then we will find that, p! has factors of
2, 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)! + 3
Then, a + 2 = (n+2)! + 4
...
Then, a + n-1 = (n+2)! + n+1
Hence,
a = (n+2)! + 2 = 2*3*....*(n+2) + 2
a has 2 as its divisor because (n+2)! and 2
both divides 2
a + 1 = 2*3*....*(n+2) + 3
a + 1 has 3 as its divisor because (n+2)!
and 3 both divides 3
...
a + n-1 = 2*3*....*(n+2) + n+1
a + n-1 has n+1 as its divisor because (n+2)!
and n+1 both divides n+1
Therefore range will be [ (n+2)! + 2, ( (n+2)! + 2 ) + n-1]
上述算法的示例
n = 3
Then a = (n+2)! + 2
a = 5! + 2
a + 1 = 5! + 3
a + 2 = 5! + 4
Here a is divisible by 2
Here a + 1 is divisible by 3
Here a + 2 is divisible by 4
Hence 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);
}
}
计算机编程语言
# 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.
服务器端编程语言(Professional Hypertext Preprocessor 的缩写)
<?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.
?>
java 描述语言
<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)
本文由 普拉蒂克·查哈尔 供稿。如果你喜欢 GeeksforGeeks 并想投稿,你也可以使用write.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客主页上,帮助其他极客。 如果发现有不正确的地方,或者想分享更多关于上述话题的信息,请写评论。
版权属于:月萌API www.moonapi.com,转载请注明出处