## Saturday, November 12, 2016

### 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;`
`}`