Exactly n distinct prime factor numbers from a to b - GeeksforGeeks

Exactly n distinct prime factor numbers from a to b - GeeksforGeeks
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.

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.

// 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];

 

    // Initalize 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;

}

Read full article from Exactly n distinct prime factor numbers from a to b - GeeksforGeeks