Data Modelling & AI Data Structure & Algorithm

Exactly n distinct prime factor numbers from a to b

23 June 2025

5

You are given two numbers a and b (1 <= a,b <= 10^8 ) and n. The task is to find all numbers between a and b inclusively having exactly n distinct prime factors. The solution should be designed in a way that it efficiently handles multiple queries for different values of a and b like in Competitive Programming.
Examples:

Input  : a = 1, b = 10, n = 2
Output : 2
// Only 6 = 2*3 and 10 = 2*5 have exactly two 
// distinct prime factors

Input : a = 1, b = 100, n = 3
Output: 8
// only 30 = 2*3*5, 42 = 2*3*7, 60 = 2*2*3*5, 66 = 2*3*11,
// 70 = 2*5*7, 78 = 2*3*13, 84 = 2*2*3*7 and 90 = 2*3*3*5 
// have exactly three distinct prime factors

This problem is basically application of segmented sieve. As we know that all prime factors of a number are always less than or equal to square root of number i.e; sqrt(n). So we generate all prime numbers less than or equals to 10^8 and store them in an array. Now using this segmented sieve we check each number from a to b to have exactly n prime factors.

C++

// C++ program to find numbers with exactly n distinct
// prime factor numbers from a to b
#include<bits/stdc++.h>
using namespace std;
 
// Stores all primes less than and equals to sqrt(10^8) = 10000
vector <int> primes;
 
// Generate all prime numbers less than or equals to sqrt(10^8)
// = 10000 using sieve of sundaram
void segmentedSieve()
{
    int n = 10000; // Square root of 10^8
 
    // In general Sieve of Sundaram, produces primes smaller
    // than (2*x + 2) for a number given number x.
    // Since we want primes smaller than n=10^4, we reduce
    // n to half
    int nNew = (n-2)/2;
 
    // This array is used to separate numbers of the form
    // i+j+2ij from others where  1 <= i <= j
    bool marked[nNew + 1];
 
    // Initialize all elements as not marked
    memset(marked, false, sizeof(marked));
 
    // Main logic of Sundaram.  Mark all numbers of the
    // form i + j + 2ij as true where 1 <= i <= j
    for (int i=1; i<=nNew; i++)
        for (int j=i; (i + j + 2*i*j) <= nNew; j++)
            marked[i + j + 2*i*j] = true;
 
    // Since 2 is a prime number
    primes.push_back(2);
 
    // Remaining primes are of the form 2*i + 1 such that
    // marked[i] is false.
    for (int i=1; i<=nNew; i++)
        if (marked[i] == false)
            primes.push_back(2*i+1);
}
 
// Function to count all numbers from a to b having exactly
// n prime factors
int Nfactors(int a, int b, int n)
{
    segmentedSieve();
 
    // result --> all numbers between a and b having
    // exactly n prime factors
    int result = 0;
 
    //  check for each number
    for (int i=a; i<=b; i++)
    {
        // tmp  --> stores square root of current number because
        //          all prime factors are always less than and
        //          equal to square root of given number
        // copy --> it holds the copy of current number
        int tmp = sqrt(i), copy = i;
 
        // count -->  it counts the number of distinct prime
        // factors of number
        int count = 0;
 
        // check divisibility of 'copy' with each prime less
        // than 'tmp' and divide it until it is divisible by
        // current prime factor
        for (int j=0; primes[j]<=tmp; j++)
        {
            if (copy%primes[j]==0)
            {
                // increment count for distinct prime
                count++;
                while (copy%primes[j]==0)
                    copy = copy/primes[j];
            }
        }
 
        // if number is completely divisible then at last
        // 'copy' will be 1 else 'copy' will be prime, so
        // increment count by one
        if (copy != 1)
            count++;
 
        // if number has exactly n distinct primes then
        // increment result by one
        if (count==n)
            result++;
    }
    return result;
}
 
// Driver program to run the case
int main()
{
    int a = 1, b = 100, n = 3;
    cout << Nfactors(a, b, n);
    return 0;
}

Java

// Java program to find numbers with exactly n distinct
// prime factor numbers from a to b
import java.util.*;
 
class GFG
{
     
// Stores all primes less than and 
// equals to sqrt(10^8) = 10000
static ArrayList<Integer> primes = new ArrayList<Integer>();
 
// Generate all prime numbers less 
// than or equals to sqrt(10^8)
// = 10000 using sieve of sundaram
static void segmentedSieve()
{
    int n = 10000; // Square root of 10^8
 
    // In general Sieve of Sundaram, 
    // produces primes smaller
    // than (2*x + 2) for a number 
    // given number x. Since we want 
    // primes smaller than n=10^4, 
    // we reduce n to half
    int nNew = (n - 2)/2;
 
    // This array is used to separate 
    // numbers of the form i+j+2ij 
    // from others where 1 <= i <= j
    boolean[] marked=new boolean[nNew + 1];
 
    // Main logic of Sundaram. Mark all 
    // numbers of the form i + j + 2ij
    // as true where 1 <= i <= j
    for (int i = 1; i <= nNew; i++)
        for (int j = i; (i + j + 2 * i * j) <= nNew; j++)
            marked[i + j + 2 * i * j] = true;
 
    // Since 2 is a prime number
    primes.add(2);
 
    // Remaining primes are of the form 2*i + 1 such that
    // marked[i] is false.
    for (int i = 1; i <= nNew; i++)
        if (marked[i] == false)
            primes.add(2 * i + 1);
}
 
// Function to count all numbers from a to b having exactly
// n prime factors
static int Nfactors(int a, int b, int n)
{
    segmentedSieve();
 
    // result --> all numbers between a and b having
    // exactly n prime factors
    int result = 0;
 
    // check for each number
    for (int i = a; i <= b; i++)
    {
        // tmp --> stores square root of current number because
        //     all prime factors are always less than and
        //     equal to square root of given number
        // copy --> it holds the copy of current number
        int tmp = (int)Math.sqrt(i), copy = i;
 
        // count --> it counts the number of distinct prime
        // factors of number
        int count = 0;
 
        // check divisibility of 'copy' with each prime less
        // than 'tmp' and divide it until it is divisible by
        // current prime factor
        for (int j = 0; primes.get(j) <= tmp; j++)
        {
            if (copy % primes.get(j) == 0)
            {
                // increment count for distinct prime
                count++;
                while (copy % primes.get(j) == 0)
                    copy = copy/primes.get(j);
            }
        }
 
        // if number is completely divisible then at last
        // 'copy' will be 1 else 'copy' will be prime, so
        // increment count by one
        if (copy != 1)
            count++;
 
        // if number has exactly n distinct primes then
        // increment result by one
        if (count == n)
            result++;
    }
    return result;
}
 
// Driver code
public static void main (String[] args) 
{
    int a = 1, b = 100, n = 3;
    System.out.println(Nfactors(a, b, n));
}
}
 
// This code is contributed by chandan_jnu

Python3

# Python3 program to find numbers with 
# exactly n distinct prime factor numbers
# from a to b
import math
 
# Stores all primes less than and 
# equals to sqrt(10^8) = 10000
primes = [];
 
# Generate all prime numbers less than 
# or equals to sqrt(10^8) = 10000
# using sieve of sundaram
def segmentedSieve():
 
    n = 10000; # Square root of 10^8
 
    # In general Sieve of Sundaram, produces
    # primes smaller than (2*x + 2) for a 
    # given number x. Since we want primes 
    # smaller than n=10^4, we reduce n to half
    nNew = int((n - 2) / 2);
 
    # This array is used to separate 
    # numbers of the form i+j+2ij
    # from others where 1 <= i <= j
    marked = [False] * (nNew + 1);
 
    # Main logic of Sundaram. Mark all 
    # numbers of the form i + j + 2ij 
    # as true where 1 <= i <= j
    for i in range(1, nNew + 1):
        j = i;
        while ((i + j + 2 * i * j) <= nNew):
            marked[i + j + 2 * i * j] = True;
            j += 1;
 
    # Since 2 is a prime number
    primes.append(2);
 
    # Remaining primes are of the 
    # form 2*i + 1 such that 
    # marked[i] is false.
    for i in range(1, nNew + 1):
        if (marked[i] == False):
            primes.append(2 * i + 1);
 
# Function to count all numbers 
# from a to b having exactly n 
# prime factors
def Nfactors(a, b, n):
 
    segmentedSieve();
 
    # result --> all numbers between 
    # a and b having exactly n prime
    # factors
    result = 0;
 
    # check for each number
    for i in range(a, b + 1):
 
        # tmp --> stores square root of  
        # current number because all prime 
        # factors are always less than and
        # equal to square root of given number
        # copy --> it holds the copy of 
        #           current number
        tmp = math.sqrt(i);
        copy = i;
 
        # count --> it counts the number of 
        # distinct prime factors of number
        count = 0;
 
        # check divisibility of 'copy' with 
        # each prime less than 'tmp' and  
        # divide it until it is divisible
        # by current prime factor
        j = 0;
        while (primes[j] <= tmp):
            if (copy % primes[j] == 0):
                 
                # increment count for
                # distinct prime
                count += 1;
                while (copy % primes[j] == 0):
                    copy = (copy // primes[j]);
            j += 1;
 
        # if number is completely divisible
        # then at last 'copy' will be 1 else 
        # 'copy' will be prime, so increment
        # count by one
        if (copy != 1):
            count += 1;
 
        # if number has exactly n distinct 
        # primes then increment result by one
        if (count == n):
            result += 1;
 
    return result;
 
# Driver Code
a = 1;
b = 100;
n = 3;
print(Nfactors(a, b, n));
 
# This code is contributed
# by chandan_jnu

C#

// C# program to find numbers with exactly n
// distinct prime factor numbers from a to b
using System;
using System.Collections;
 
class GFG
{
     
// Stores all primes less than and 
// equals to sqrt(10^8) = 10000
static ArrayList primes = new ArrayList();
 
// Generate all prime numbers less 
// than or equals to sqrt(10^8)
// = 10000 using sieve of sundaram
static void segmentedSieve()
{
    int n = 10000; // Square root of 10^8
 
    // In general Sieve of Sundaram, produces 
    // primes smaller than (2*x + 2) for a number 
    // given number x. Since we want primes 
    // smaller than n=10^4, we reduce n to half
    int nNew = (n - 2) / 2;
 
    // This array is used to separate 
    // numbers of the form i+j+2ij 
    // from others where 1 <= i <= j
    bool[] marked = new bool[nNew + 1];
 
    // Main logic of Sundaram. Mark all 
    // numbers of the form i + j + 2ij
    // as true where 1 <= i <= j
    for (int i = 1; i <= nNew; i++)
        for (int j = i; 
            (i + j + 2 * i * j) <= nNew; j++)
            marked[i + j + 2 * i * j] = true;
 
    // Since 2 is a prime number
    primes.Add(2);
 
    // Remaining primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for (int i = 1; i <= nNew; i++)
        if (marked[i] == false)
            primes.Add(2 * i + 1);
}
 
// Function to count all numbers from 
// a to b having exactly n prime factors
static int Nfactors(int a, int b, int n)
{
    segmentedSieve();
 
    // result --> all numbers between a and b 
    // having exactly n prime factors
    int result = 0;
 
    // check for each number
    for (int i = a; i <= b; i++)
    {
        // tmp --> stores square root of current
        // number because all prime factors are 
        // always less than and equal to square 
        // root of given number
        // copy --> it holds the copy of current number
        int tmp = (int)Math.Sqrt(i), copy = i;
 
        // count --> it counts the number of 
        // distinct prime factors of number
        int count = 0;
 
        // check divisibility of 'copy' with each 
        // prime less than 'tmp' and divide it until 
        // it is divisible by current prime factor
        for (int j = 0; (int)primes[j] <= tmp; j++)
        {
            if (copy % (int)primes[j] == 0)
            {
                // increment count for distinct prime
                count++;
                while (copy % (int)primes[j] == 0)
                    copy = copy / (int)primes[j];
            }
        }
 
        // if number is completely divisible then 
        // at last 'copy' will be 1 else 'copy' 
        // will be prime, so increment count by one
        if (copy != 1)
            count++;
 
        // if number has exactly n distinct 
        // primes then increment result by one
        if (count == n)
            result++;
    }
    return result;
}
 
// Driver code
public static void Main() 
{
    int a = 1, b = 100, n = 3;
    Console.WriteLine(Nfactors(a, b, n));
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP program to find numbers with exactly n 
// distinct prime factor numbers from a to b
 
// Stores all primes less than and equals 
// to sqrt(10^8) = 10000
$primes = array();
 
// Generate all prime numbers less than or 
// equals to sqrt(10^8) = 10000 using
// sieve of sundaram
function segmentedSieve()
{
    global $primes;
    $n = 10000; // Square root of 10^8
 
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a 
    // given number x. Since we want primes 
    // smaller than n=10^4, we reduce n to half
    $nNew = (int)(($n-2)/2);
 
    // This array is used to separate numbers of 
    // the form i+j+2ij from others where 1 <= i <= j
    $marked = array_fill(0, $nNew + 1, false);
 
    // Main logic of Sundaram. Mark all numbers of the
    // form i + j + 2ij as true where 1 <= i <= j
    for ($i = 1; $i <= $nNew; $i++)
        for ($j = $i; 
            ($i + $j + 2 * $i * $j) <= $nNew; $j++)
            $marked[$i + $j + 2 * $i * $j] = true;
 
    // Since 2 is a prime number
    array_push($primes, 2);
 
    // Remaining primes are of the form 2*i + 1 
    // such that marked[i] is false.
    for ($i = 1; $i <= $nNew; $i++)
        if ($marked[$i] == false)
            array_push($primes, 2 * $i + 1);
}
 
// Function to count all numbers from a to b 
// having exactly n prime factors
function Nfactors($a, $b, $n)
{
    global $primes;
    segmentedSieve();
 
    // result --> all numbers between a and b 
    // having exactly n prime factors
    $result = 0;
 
    // check for each number
    for ($i = $a; $i <= $b; $i++)
    {
        // tmp --> stores square root of current 
        // number because all prime factors are 
        // always less than and equal to square
        // root of given number
        // copy --> it holds the copy of current number
        $tmp = sqrt($i);
        $copy = $i;
 
        // count --> it counts the number of 
        // distinct prime factors of number
        $count = 0;
 
        // check divisibility of 'copy' with each 
        // prime less than 'tmp' and divide it until 
        // it is divisible by current prime factor
        for ($j = 0; $primes[$j] <= $tmp; $j++)
        {
            if ($copy % $primes[$j] == 0)
            {
                // increment count for distinct prime
                $count++;
                while ($copy % $primes[$j] == 0)
                    $copy = (int)($copy / $primes[$j]);
            }
        }
 
        // if number is completely divisible then 
        // at last 'copy' will be 1 else 'copy' 
        // will be prime, so increment count by one
        if ($copy != 1)
            $count++;
 
        // if number has exactly n distinct primes 
        // then increment result by one
        if ($count == $n)
            $result++;
    }
    return $result;
}
 
// Driver Code
$a = 1;
$b = 100;
$n = 3;
print(Nfactors($a, $b, $n));
 
// This code is contributed by chandan_jnu
?>

Javascript

<script>
 
    // JavaScript program to find numbers with exactly n
    // distinct prime factor numbers from a to b
     
    // Stores all primes less than and 
    // equals to sqrt(10^8) = 10000
    let primes = [];
 
    // Generate all prime numbers less 
    // than or equals to sqrt(10^8)
    // = 10000 using sieve of sundaram
    function segmentedSieve()
    {
        let n = 10000; // Square root of 10^8
 
        // In general Sieve of Sundaram, produces 
        // primes smaller than (2*x + 2) for a number 
        // given number x. Since we want primes 
        // smaller than n=10^4, we reduce n to half
        let nNew = parseInt((n - 2) / 2, 10);
 
        // This array is used to separate 
        // numbers of the form i+j+2ij 
        // from others where 1 <= i <= j
        let marked = new Array(nNew + 1);
        marked.fill(false);
 
        // Main logic of Sundaram. Mark all 
        // numbers of the form i + j + 2ij
        // as true where 1 <= i <= j
        for (let i = 1; i <= nNew; i++)
            for (let j = i; 
                (i + j + 2 * i * j) <= nNew; j++)
                marked[i + j + 2 * i * j] = true;
 
        // Since 2 is a prime number
        primes.push(2);
 
        // Remaining primes are of the form
        // 2*i + 1 such that marked[i] is false.
        for (let i = 1; i <= nNew; i++)
            if (marked[i] == false)
                primes.push(2 * i + 1);
    }
 
    // Function to count all numbers from 
    // a to b having exactly n prime factors
    function Nfactors(a, b, n)
    {
        segmentedSieve();
 
        // result --> all numbers between a and b 
        // having exactly n prime factors
        let result = 0;
 
        // check for each number
        for (let i = a; i <= b; i++)
        {
            // tmp --> stores square root of current
            // number because all prime factors are 
            // always less than and equal to square 
            // root of given number
            // copy --> it holds the copy of current number
            let tmp = parseInt(Math.sqrt(i), 10), copy = i;
 
            // count --> it counts the number of 
            // distinct prime factors of number
            let count = 0;
 
            // check divisibility of 'copy' with each 
            // prime less than 'tmp' and divide it until 
            // it is divisible by current prime factor
            for (let j = 0; primes[j] <= tmp; j++)
            {
                if (copy % primes[j] == 0)
                {
                    // increment count for distinct prime
                    count++;
                    while (copy % primes[j] == 0)
                        copy = parseInt(copy / primes[j], 10);
                }
            }
 
            // if number is completely divisible then 
            // at last 'copy' will be 1 else 'copy' 
            // will be prime, so increment count by one
            if (copy != 1)
                count++;
 
            // if number has exactly n distinct 
            // primes then increment result by one
            if (count == n)
                result++;
        }
        return result;
    }
     
    let a = 1, b = 100, n = 3;
    document.write(Nfactors(a, b, n));
     
</script>

Output:

If you have another approach to solve this problem then please share in comments.
This article is contributed by Shashank Mishra ( Gullu ). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

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 neveropen!

4 COMMENTS

click để xem 11 May 2026 At 12:10 am

… [Trackback]

[…] Find More Info here on that Topic: geeksforgeeks.org/exactly-n-distinct-prime-factor-numbers-from-a-to-b/ […]

Log in to leave a comment
https://backlink-market.com 11 May 2026 At 12:10 am

… [Trackback]

[…] Find More Information here to that Topic: geeksforgeeks.org/exactly-n-distinct-prime-factor-numbers-from-a-to-b/ […]

Log in to leave a comment
https://chintamani.kz/hatha-yoga-online/ 11 May 2026 At 5:17 pm

… [Trackback]

[…] Read More here on that Topic: geeksforgeeks.org/exactly-n-distinct-prime-factor-numbers-from-a-to-b/ […]

Log in to leave a comment
https://7bitcasino-zerkalo.it.com 3 July 2026 At 2:07 am

… [Trackback]

[…] Read More on that Topic: geeksforgeeks.org/exactly-n-distinct-prime-factor-numbers-from-a-to-b/ […]

Log in to leave a comment

Exactly n distinct prime factor numbers from a to b

C++

Java

Python3

C#

PHP

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

4 COMMENTS

LEAVE A REPLY Cancel reply

Most Popular

iOS 27 Vs. Android 17 reveals a LOT. [Video]

Your Pixel phone could get a big under-the-hood upgrade this year

Android 17 QPR1 Beta 6 hits Pixel phones with a major milestone for developers

Samsung’s Galaxy S27 Pro could finally fix what was wrong with the Plus

EDITOR PICKS

iOS 27 Vs. Android 17 reveals a LOT. [Video]

Your Pixel phone could get a big under-the-hood upgrade this year

Android 17 QPR1 Beta 6 hits Pixel phones with a major milestone for developers

POPULAR POSTS

iOS 27 Vs. Android 17 reveals a LOT. [Video]

Your Pixel phone could get a big under-the-hood upgrade this year

Android 17 QPR1 Beta 6 hits Pixel phones with a major milestone for developers

POPULAR CATEGORY

ABOUT US

FOLLOW US