text: First element of every K sets having consecutive elements with exactly K prime factors less than N | C ++ program for the above approach ; For storing smallest prime factor ; Function construct smallest prime factor array ; Mark smallest prime factor for every number to be itself . ; separately mark spf for every even number as 2 ; Check if i is prime ; Mark SPF for all numbers divisible by i ; Mark spf [ j ] if it is not previously marked ; Function for counts total number of prime factors ; Function to print elements of sets of K consecutive elements having K prime factors ; To store the result ; Count number of prime factors of number ; If number has exactly K factors push in result [ ] ; Iterate till we get K consecutive elements in result [ ] ; Count sequence until K ; Print the element if count >= K ; Driver Code ; To construct spf [ ] ; Given N and K ; Function Call
code: #include <bits/stdc++.h> NEW_LINE #define x  2000021 NEW_LINE using namespace std ; long long int v [ x ] ; void sieve ( ) { v [ 1 ] = 1 ; for ( long long int i = 2 ; i < x ; i ++ ) v [ i ] = i ; for ( long long int i = 4 ; i < x ; i += 2 ) v [ i ] = 2 ; for ( long long int i = 3 ; i * i < x ; i ++ ) { if ( v [ i ] == i ) { for ( long long int j = i * i ; j < x ; j += i ) { if ( v [ j ] == j ) { v [ j ] = i ; } } } } } long long int prime_factors ( long long n ) { set < long long int > s ; while ( n != 1 ) { s . insert ( v [ n ] ) ; n = n / v [ n ] ; } return s . size ( ) ; } void distinctPrimes ( long long int m , long long int k ) { vector < long long int > result ; for ( long long int i = 14 ; i < m + k ; i ++ ) { long long count = prime_factors ( i ) ; if ( count == k ) { result . push_back ( i ) ; } } long long int p = result . size ( ) ; for ( long long int index = 0 ; index < p - 1 ; index ++ ) { long long element = result [ index ] ; long long count = 1 , z = index ; while ( z < p - 1 && count <= k && result [ z ] + 1 == result [ z + 1 ] ) { count ++ ; z ++ ; } if ( count >= k ) cout << element << ' ▁ ' ; } } int main ( ) { sieve ( ) ; long long int N = 1000 , K = 3 ; distinctPrimes ( N , K ) ; return 0 ; }