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 Nint p[M + 1];Â
// Array to store whether each integer from// 1 to N is prime or notbool 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 arrayint 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 Codeint main(){Â Â Â Â int L = 1, R = 5;Â
    // Function call    int answer = countNum(L, R);    cout << answer;    return 0;} |
Java
// Java code to implement the above approachimport 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 approachimport mathÂ
M = int(1e5)Â
# Array to store primes upto each# integer from 1 to Np = [0 for _ in range(M + 1)]Â
# Array to store whether each integer from# 1 to N is prime or notisPrime = [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 arraydef 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 Codeif __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 approachusing 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
3
Time Complexity: O(M*log(log(M))), where M is 1e5
Auxiliary Space: O(M)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
