Count of integers in range [L, R] not forming any Triangular Pair with number in [1, R]

0 0 7 minutes read

Given integers L and R, the task is to find the number of integers in range [L, R] (say X) which does not form a triangular pair with any other integer in the range [1, R].

Note: A pair of integers {X, Y} is called a triangular pair if GCD(X, Y), X/GCD(X, Y) and Y/GCD(X, Y) can form sides of a triangle.

Examples:

Input: L = 1, R = 5
Output: 3
Explanation: In range [1, 5] there are 3 elements 1, 3 and 5 which does not form any triangular pair.
Other integers 2 and 4 can form triangular pairs. the pair(2, 4) is a triangular pair.
GCD(2, 4) = 2. So the triplet formed is (2, 4/2, 2/2) = (2, 2, 1).
This can be sides of a valid triangle. So only 3 elements are there.

Input: L = 2, R = 6
Output: 2

Approach: The problem can be solved based on the following observation:

From 1 to N, only 1 and the prime numbers in the range √N to N does not form triangular pairs with any other integers in the range 1 to N

The above observation can be justified as shown below:

Proof :

For composite numbers: All the composite numbers will form triangular pair with atleast 1 integer.

Suppose x is a composite number, then x = y * z (y ≥ z, y ≥ 2, z ≥ 2).

Let a be another number such that a = ((y-1)*z).

So gcd(a, x) = z, a/gcd(a, x) = y – 1 and x/gcd(a, x) = y.

The triplet {y, y-1, z} would obviously form the sides of a triangle.

For prime numbers: Consider any prime number p in the range [1, N] and any non-coprime number of p, say a.

So, gcd(a, p) = p, a/gcd(a, p) = a/p and p/gcd(a, p) = 1.

Now, for the pair {a, p} to form a triangular pair, {1, p, a/p} must form a triangle.

For that, (p+1) > a/p and 1 + a/p > p, which is possible only when p = a/p or p = √a.

That means, prime number p in range 1 to N can form triangular pair with another integer if p ≤ √N.

So, it can be concluded that in the range [1, N], the integer 1 and prime numbers larger than √N cannot form triangular pairs with any other integers in the range.

So the numbers in range [L, R] which does not form any triangular pair can be calculated by finding such numbers in range [1, L) (say C1) and in range [1, R] (say C2) and then subtracting C1 from C2.

Follow the steps mentioned below to implement the above observation:

Store the number of prime numbers till each integer from 1 to R using sieve of eratosthenes.
Calculate C1 and C2 as shown in the above observation.
Subtract C1 from C2 (say count).
Return count as the final answer.

Below is the implementation of the above approach:

C++

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5;
 
// Array to store primes upto each
// integer from 1 to N
int p[M + 1];
 
// Array to store whether each integer from
// 1 to N is prime  or not
bool isPrime[M + 1];
 
// Function to count integers in given
// range which does not form a triangle
// with any other integer in the same
// range for all  elements of array
int countNum(int L, int R)
{
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = false, isPrime[1] = false;
 
    // Standard sieve method to store
    // which integer is prime
    for (int i = 2; i * i <= R; i++) {
        if (isPrime[i] == true) {
            for (int j = i * i; j <= R;
                 j += i) {
                isPrime[j] = false;
            }
        }
    }
 
    // Prefix sum method to store total primes
    // upto any integer till M
    p[0] = 0;
    for (int i = 1; i <= R; i++) {
        p[i] = p[i - 1];
        if (isPrime[i]) {
            p[i]++;
        }
    }
 
    // Though 2 is prime but it is even also
    p[1] = 1;
    int count = p[R] - p[L - 1];
 
    // Returning answer
    return count;
}
 
// Driver Code
int main()
{
    int L = 1, R = 5;
 
    // Function call
    int answer = countNum(L, R);
    cout << answer;
    return 0;
}

Java

// Java code to implement the above approach
import java.io.*;
 
class GFG 
{
 
  // Function to count integers in given
  // range which does not form a triangle
  // with any other integer in the same
  // range for all  elements of array
  public static int countNum(int L, int R)
  {
 
    // Array to store primes upto each
    // integer from 1 to N
    int p[] = new int[100001];
 
    // Array to store whether each integer from
    // 1 to N is prime  or not
    boolean isPrime[] = new boolean[100001];
    for (int i = 0; i < 100001; i++)
      isPrime[i] = true;
 
    isPrime[0] = false;
    isPrime[1] = false;
 
    // Standard sieve method to store
    // which integer is prime
    for (int i = 2; i * i <= R; i++) {
      if (isPrime[i] == true) {
        for (int j = i * i; j <= R; j += i) {
          isPrime[j] = false;
        }
      }
    }
 
    // Prefix sum method to store total primes
    // upto any integer till M
    p[0] = 0;
    for (int i = 1; i <= R; i++) {
      p[i] = p[i - 1];
      if (isPrime[i] == true) {
        p[i]++;
      }
    }
 
    // Though 2 is prime but it is even also
    p[1] = 1;
    int count = p[R] - p[L - 1];
 
    // Returning answer
    return count;
  }
 
  public static void main(String[] args)
  {
    int L = 1, R = 5;
 
    // Function call
    int answer = countNum(L, R);
    System.out.print(answer);
  }
}
 
// This code is contributed by Rohit Pradhan.

Python3

# python3 code to implement the above approach
import math
 
M = int(1e5)
 
# Array to store primes upto each
# integer from 1 to N
p = [0 for _ in range(M + 1)]
 
# Array to store whether each integer from
# 1 to N is prime or not
isPrime = [True for _ in range(M + 1)]
 
# Function to count integers in given
# range which does not form a triangle
# with any other integer in the same
# range for all elements of array
def countNum(L, R):
    global isPrime
 
    isPrime[0], isPrime[1] = False, False
 
    # Standard sieve method to store
    # which integer is prime
    for i in range(2, int(math.sqrt(R)) + 1):
        if (isPrime[i] == True):
            for j in range(i*i, R+1, i):
                isPrime[j] = False
 
        # Prefix sum method to store total primes
        # upto any integer till M
    p[0] = 0
 
    for i in range(1, R+1):
        p[i] = p[i - 1]
        if (isPrime[i]):
            p[i] += 1
 
        # Though 2 is prime but it is even also
    p[1] = 1
    count = p[R] - p[L - 1]
 
    # Returning answer
    return count
 
# Driver Code
if __name__ == "__main__":
 
    L, R = 1, 5
 
    # Function call
    answer = countNum(L, R)
    print(answer)
 
    # This code is contributed by rakeshsahni

C#

// C# code to implement the above approach
using System;
class GFG
{
 
  static int M = 100000;
 
  // Array to store primes upto each
  // integer from 1 to N
  static int[] p = new int[M + 1];
 
  // Array to store whether each integer from
  // 1 to N is prime  or not
  static bool[] isPrime = new bool[M + 1];
 
  // Function to count integers in given
  // range which does not form a triangle
  // with any other integer in the same
  // range for all  elements of array
  static int countNum(int L, int R)
  {
    for (int i = 0; i < M + 1; i++) {
      isPrime[i] = true;
    }
 
    isPrime[0] = false;
    isPrime[1] = false;
 
    // Standard sieve method to store
    // which integer is prime
    for (int i = 2; i * i <= R; i++) {
      if (isPrime[i] == true) {
        for (int j = i * i; j <= R; j += i) {
          isPrime[j] = false;
        }
      }
    }
 
    // Prefix sum method to store total primes
    // upto any integer till M
    p[0] = 0;
    for (int i = 1; i <= R; i++) {
      p[i] = p[i - 1];
      if (isPrime[i]) {
        p[i]++;
      }
    }
 
    // Though 2 is prime but it is even also
    p[1] = 1;
    int count = p[R] - p[L - 1];
 
    // Returning answer
    return count;
  }
 
  // Driver Code
  public static void Main()
  {
    int L = 1, R = 5;
 
    // Function call
    int answer = countNum(L, R);
    Console.Write(answer);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript code for the above approach
    let M = 1e5;
 
    // Array to store primes upto each
    // integer from 1 to N
    let p = new Array(M + 1);
 
    // Array to store whether each integer from
    // 1 to N is prime  or not
    let isPrime = new Array(M + 1).fill(true);
 
    // Function to count integers in given
    // range which does not form a triangle
    // with any other integer in the same
    // range for all  elements of array
    function countNum(L, R) 
    {
        isPrime[0] = false, isPrime[1] = false;
 
        // Standard sieve method to store
        // which integer is prime
        for (let i = 2; i * i <= R; i++) {
            if (isPrime[i] == true) {
                for (let j = i * i; j <= R;
                    j += i) {
                    isPrime[j] = false;
                }
            }
        }
 
        // Prefix sum method to store total primes
        // upto any integer till M
        p[0] = 0;
        for (let i = 1; i <= R; i++) {
            p[i] = p[i - 1];
            if (isPrime[i]) {
                p[i]++;
            }
        }
 
        // Though 2 is prime but it is even also
        p[1] = 1;
        let count = p[R] - p[L - 1];
 
        // Returning answer
        return count;
    }
 
    // Driver Code
    let L = 1, R = 5;
 
    // Function call
    let answer = countNum(L, R);
    document.write(answer);
 
    // This code is contributed by Potta Lokesh
</script>

Output

Time Complexity: O(M*log(log(M))), where M is 1e5
Auxiliary Space: O(M)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!