# Untitled

unknown
c_cpp
3 years ago
3.0 kB
3
Indexable
Never
```// 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;
}```