# Count numbers from a given range having exactly 5 distinct factors

Given two integers **L **and **R**, the task is to calculate the count of numbers from the range** [L, R]** having exactly **5 distinct positive factors.**

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:L = 1, R= 100Output:2Explanation:The only two numbers in the range [1, 100] having exactly 5 prime factors are 16 and 81.

Factors of 16 are {1, 2, 4, 8, 16}.

Factors of 8 are {1, 3, 9, 27, 81}.

Input:L = 1, R= 100Output:2

**Naive Approach:** The simplest approach to solve this problem is to traverse the range **[L, R] **and for every number, count its factors. If the count of factors is equal to **5**, increment count by **1**. **Time Complexity: **(R – L) × √N **Auxiliary Space:** O(1)**Efficient Approach:** To optimize the above approach, the following observation needs to be made regarding numbers having exactly 5 factors.

Let the prime factorization of a number be p

_{1}^{a}_{1}×p_{2}^{a}_{2}× … ×p_{n}^{a}_{n}.

Therefore, the count of factors of this number can be written as (a_{1}+ 1)×(a_{2}+ 1)× … ×(a_{n}+ 1).

Since this product must be equal to5(which is a prime number), only one term greater than 1 must exist in the product. That term must be equal to 5.

Therefore, if a_{i}+ 1 = 5

=> a_{i}= 4

Follow the steps below to solve the problem:

- The required count is the count of numbers in the range containing p
^{4}as a factor, where**p**is a prime number. - For efficiently calculating p
^{4}for a large range (**[1, 10**), the idea is to use Sieve of Eratosthenes to store all prime numbers up to^{18}]**10**^{4.5}.

Below is the implementation of the above approach:

## C++14

`// C++ Program to implement` `// the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `N = 2e5;` `// Stores all prime numbers` `// up to 2 * 10^5` `vector<` `long` `long` `> prime;` `// Function to generate all prime` `// numbers up to 2 * 10 ^ 5 using` `// Sieve of Eratosthenes` `void` `Sieve()` `{` ` ` `prime.clear();` ` ` `vector<` `bool` `> p(N + 1, ` `true` `);` ` ` `// Mark 0 and 1 as non-prime` ` ` `p[0] = p[1] = ` `false` `;` ` ` `for` `(` `int` `i = 2; i * i <= N; i++) {` ` ` `// If i is prime` ` ` `if` `(p[i] == ` `true` `) {` ` ` `// Mark all its factors as non-prime` ` ` `for` `(` `int` `j = i * i; j <= N; j += i) {` ` ` `p[j] = ` `false` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `for` `(` `int` `i = 1; i < N; i++) {` ` ` `// If current number is prime` ` ` `if` `(p[i]) {` ` ` `// Store the prime` ` ` `prime.push_back(1LL * ` `pow` `(i, 4));` ` ` `}` ` ` `}` `}` `// Function to count numbers in the` `// range [L, R] having exactly 5 factors` `void` `countNumbers(` `long` `long` `int` `L,` ` ` `long` `long` `int` `R)` `{` ` ` `// Stores the required count` ` ` `int` `Count = 0;` ` ` `for` `(` `int` `p : prime) {` ` ` `if` `(p >= L && p <= R) {` ` ` `Count++;` ` ` `}` ` ` `}` ` ` `cout << Count << endl;` `}` `// Driver Code` `int` `main()` `{` ` ` `long` `long` `L = 16, R = 85000;` ` ` `Sieve();` ` ` `countNumbers(L, R);` ` ` `return` `0;` `}` |

## Java

`// Java Program to implement` `// the above approach` `import` `java.util.*;` `class` `GFG` `{` ` ` `static` `int` `N = ` `200000` `;` ` ` `// Stores all prime numbers` ` ` `// up to 2 * 10^5` ` ` `static` `int` `prime[] = ` `new` `int` `[` `20000` `];` ` ` `static` `int` `index = ` `0` `;` ` ` `// Function to generate all prime` ` ` `// numbers up to 2 * 10 ^ 5 using` ` ` `// Sieve of Eratosthenes` ` ` `static` `void` `Sieve()` ` ` `{` ` ` `index = ` `0` `;` ` ` `int` `p[] = ` `new` `int` `[N + ` `1` `];` ` ` `for` `(` `int` `i = ` `0` `; i <= N; i++)` ` ` `{` ` ` `p[i] = ` `1` `;` ` ` `}` ` ` `// Mark 0 and 1 as non-prime` ` ` `p[` `0` `] = p[` `1` `] = ` `0` `;` ` ` `for` `(` `int` `i = ` `2` `; i * i <= N; i++)` ` ` `{` ` ` `// If i is prime` ` ` `if` `(p[i] == ` `1` `)` ` ` `{` ` ` `// Mark all its factors as non-prime` ` ` `for` `(` `int` `j = i * i; j <= N; j += i)` ` ` `{` ` ` `p[j] = ` `0` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `for` `(` `int` `i = ` `1` `; i < N; i++)` ` ` `{` ` ` `// If current number is prime` ` ` `if` `(p[i] == ` `1` `)` ` ` `{` ` ` `// Store the prime` ` ` `prime[index++] = (` `int` `)(Math.pow(i, ` `4` `));` ` ` `}` ` ` `}` ` ` `}` ` ` `// Function to count numbers in the` ` ` `// range [L, R] having exactly 5 factors` ` ` `static` `void` `countNumbers(` `int` `L,` `int` `R)` ` ` `{` ` ` `// Stores the required count` ` ` `int` `Count = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < index; i++)` ` ` `{` ` ` `int` `p = prime[i];` ` ` `if` `(p >= L && p <= R)` ` ` `{` ` ` `Count++;` ` ` `}` ` ` `}` ` ` `System.out.println(Count);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `L = ` `16` `, R = ` `85000` `;` ` ` `Sieve();` ` ` `countNumbers(L, R);` ` ` `}` `}` `// This code is contributed by amreshkumar3.` |

## Python3

`# Python3 implementation of` `# the above approach` `N ` `=` `2` `*` `100000` `# Stores all prime numbers` `# up to 2 * 10^5` `prime ` `=` `[` `0` `] ` `*` `N` `# Function to generate all prime` `# numbers up to 2 * 10 ^ 5 using` `# Sieve of Eratosthenes` `def` `Sieve() :` ` ` `p ` `=` `[` `True` `] ` `*` `(N ` `+` `1` `)` ` ` `# Mark 0 and 1 as non-prime` ` ` `p[` `0` `] ` `=` `p[` `1` `] ` `=` `False` ` ` `i ` `=` `2` ` ` `while` `(i ` `*` `i <` `=` `N) :` ` ` `# If i is prime` ` ` `if` `(p[i] ` `=` `=` `True` `) :` ` ` `# Mark all its factors as non-prime` ` ` `for` `j ` `in` `range` `(i ` `*` `i, N, i):` ` ` `p[j] ` `=` `False` ` ` `i ` `+` `=` `1` ` ` `for` `i ` `in` `range` `(N):` ` ` `# If current number is prime` ` ` `if` `(p[i] !` `=` `False` `) :` ` ` `# Store the prime` ` ` `prime.append(` `pow` `(i, ` `4` `))` `# Function to count numbers in the` `# range [L, R] having exactly 5 factors` `def` `countNumbers(L, R) :` ` ` `# Stores the required count` ` ` `Count ` `=` `0` ` ` `for` `p ` `in` `prime :` ` ` `if` `(p >` `=` `L ` `and` `p <` `=` `R) :` ` ` `Count ` `+` `=` `1` ` ` `print` `(Count)` `# Driver Code` `L ` `=` `16` `R ` `=` `85000` `Sieve()` `countNumbers(L, R)` `# This code is contributed by code_hunt.` |

## C#

`// C# Program to implement` `// the above approach` `using` `System;` `class` `GFG` `{` ` ` `static` `int` `N = 200000;` ` ` `// Stores all prime numbers` ` ` `// up to 2 * 10^5` ` ` `static` `int` `[]prime = ` `new` `int` `[20000];` ` ` `static` `int` `index = 0;` ` ` `// Function to generate all prime` ` ` `// numbers up to 2 * 10 ^ 5 using` ` ` `// Sieve of Eratosthenes` ` ` `static` `void` `Sieve()` ` ` `{` ` ` `index = 0;` ` ` `int` `[]p = ` `new` `int` `[N + 1];` ` ` `for` `(` `int` `i = 0; i <= N; i++)` ` ` `{` ` ` `p[i] = 1;` ` ` `}` ` ` `// Mark 0 and 1 as non-prime` ` ` `p[0] = p[1] = 0;` ` ` `for` `(` `int` `i = 2; i * i <= N; i++)` ` ` `{` ` ` `// If i is prime` ` ` `if` `(p[i] == 1)` ` ` `{` ` ` `// Mark all its factors as non-prime` ` ` `for` `(` `int` `j = i * i; j <= N; j += i)` ` ` `{` ` ` `p[j] = 0;` ` ` `}` ` ` `}` ` ` `}` ` ` `for` `(` `int` `i = 1; i < N; i++)` ` ` `{` ` ` `// If current number is prime` ` ` `if` `(p[i] == 1)` ` ` `{` ` ` `// Store the prime` ` ` `prime[index++] = (` `int` `)(Math.Pow(i, 4));` ` ` `}` ` ` `}` ` ` `}` ` ` `// Function to count numbers in the` ` ` `// range [L, R] having exactly 5 factors` ` ` `static` `void` `countNumbers(` `int` `L,` `int` `R)` ` ` `{` ` ` `// Stores the required count` ` ` `int` `Count = 0;` ` ` `for` `(` `int` `i = 0; i < index; i++)` ` ` `{` ` ` `int` `p = prime[i];` ` ` `if` `(p >= L && p <= R)` ` ` `{` ` ` `Count++;` ` ` `}` ` ` `}` ` ` `Console.WriteLine(Count);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `int` `L = 16, R = 85000;` ` ` `Sieve();` ` ` `countNumbers(L, R);` ` ` `}` `}` `// This code is contributed by shikhasingrajput` |

## Javascript

`<script>` `// javascript program of the above approach` `let N = 200000;` ` ` ` ` `// Stores all prime numbers` ` ` `// up to 2 * 10^5` ` ` `let prime = ` `new` `Array(20000).fill(0);` ` ` `let index = 0;` ` ` ` ` `// Function to generate all prime` ` ` `// numbers up to 2 * 10 ^ 5 using` ` ` `// Sieve of Eratosthenes` ` ` `function` `Sieve()` ` ` `{` ` ` `index = 0;` ` ` `let p = ` `new` `Array (N + 1).fill(0);` ` ` `for` `(let i = 0; i <= N; i++)` ` ` `{` ` ` `p[i] = 1;` ` ` `}` ` ` ` ` `// Mark 0 and 1 as non-prime` ` ` `p[0] = p[1] = 0;` ` ` `for` `(let i = 2; i * i <= N; i++)` ` ` `{` ` ` ` ` `// If i is prime` ` ` `if` `(p[i] == 1)` ` ` `{` ` ` ` ` `// Mark all its factors as non-prime` ` ` `for` `(let j = i * i; j <= N; j += i)` ` ` `{` ` ` `p[j] = 0;` ` ` `}` ` ` `}` ` ` `}` ` ` `for` `(let i = 1; i < N; i++)` ` ` `{` ` ` ` ` `// If current number is prime` ` ` `if` `(p[i] == 1)` ` ` `{` ` ` ` ` `// Store the prime` ` ` `prime[index++] = (Math.pow(i, 4));` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// Function to count numbers in the` ` ` `// range [L, R] having exactly 5 factors` ` ` `function` `countNumbers(L, R)` ` ` `{` ` ` ` ` `// Stores the required count` ` ` `let Count = 0;` ` ` `for` `(let i = 0; i < index; i++)` ` ` `{` ` ` `let p = prime[i];` ` ` `if` `(p >= L && p <= R)` ` ` `{` ` ` `Count++;` ` ` `}` ` ` `}` ` ` `document.write(Count);` ` ` `}` ` ` `// Driver Code` ` ` ` ` `let L = 16, R = 85000;` ` ` `Sieve();` ` ` `countNumbers(L, R);` `</script>` |

**Output:**

7

**Time Complexity: **O(N * log(log(N)) )**Auxiliary Space:** O(N)