Tutorialspoint.dev

Find a range of composite numbers of given length

Given an integer n, we need to find a range of positive integers such that all the number in that range are composite and length of that range is n. You may print anyone range in the case of more than one answer. A composite number is a positive integer that has at least one divisor other than 1 and itself (Source : wiki )

Examples :

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



The solution is little tricky. Since there are many possible answers, we discuss a generalized solution here.

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]

Example for above algorithm

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 contributd 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

# 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.

/div>

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 contributd by anuj_67.
?>


Output :

[122, 124]

Analysis of above algorithm
Time Complexity : O(n)
Auxiliary Space : O(1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter