AA k-Almost Prime Number is a number having exactly k prime factors (not necessarily distinct).
For example,
2, 3, 5, 7, 11 ….(in fact all prime numbers) are 1-Almost Prime Numbers as they have only 1 prime factor (which is themselves). 4, 6, 9…. are 2-Almost Prime Numbers as they have exactly 2 prime factors (4 = 2*2, 6 = 2*3, 9 = 3*3) Similarly, 32 is a 5-Almost Prime Number (32 = 2*2*2*2*2) and so is 72 (2*2*2*3*3) All the 1-Almost Primes are called as Prime Numbers and all the 2-Almost Prime are called semi-primes. The task is to print first n numbers that are k prime.
Examples:
Input: k = 2, n = 5 Output: 4 6 9 10 14 4 has two prime factors, 2 x 2 6 has two prime factors, 2 x 3 Similarly, 9(3 x 3), 10(2 x 5) and 14(2 x 7) Input: k = 10, n = 2 Output: 1024 1536 1024 and 1536 are first two numbers with 10 prime factors.
We iterate natural numbers and keep printing k-primes till the count of printed k-primes is less than or equal to n. To check if a number is k-prime, we find count of prime factors and if the count is k we consider the number as k-prime.
Below is the implementation of the above approach :
C++
// Program to print first n numbers that are k-primes#include<bits/stdc++.h>using namespace std;// A function to count all prime factors of a given numberint countPrimeFactors(int n){ int count = 0; // Count the number of 2s that divide n while (n%2 == 0) { n = n/2; count++; } // n must be odd at this point. So we can skip one // element (Note i = i +2) for (int i = 3; i <= sqrt(n); i = i+2) { // While i divides n, count i and divide n while (n%i == 0) { n = n/i; count++; } } // This condition is to handle the case when n is a // prime number greater than 2 if (n > 2) count++; return(count);}// A function to print the first n numbers that are// k-almost primes.void printKAlmostPrimes(int k, int n){ for (int i=1, num=2; i<=n; num++) { // Print this number if it is k-prime if (countPrimeFactors(num) == k) { printf("%d ", num); // Increment count of k-primes printed // so far i++; } } return;}/* Driver program to test above function */int main(){ int n = 10, k = 2; printf("First %d %d-almost prime numbers : \n", n, k); printKAlmostPrimes(k, n); return 0;} |
Java
// Program to print first n numbers that // are k-primesimport java.io.*;class GFG { // A function to count all prime factors // of a given number static int countPrimeFactors(int n) { int count = 0; // Count the number of 2s that divide n while (n % 2 == 0) { n = n / 2; count++; } // n must be odd at this point. So we // can skip one element (Note i = i +2) for (int i = 3; i <= Math.sqrt(n); i = i + 2) { // While i divides n, count i and // divide n while (n % i == 0) { n = n / i; count++; } } // This condition is to handle the case // when n is a prime number greater // than 2 if (n > 2) count++; return (count); } // A function to print the first n numbers // that are k-almost primes. static void printKAlmostPrimes(int k, int n) { for (int i = 1, num = 2; i <= n; num++) { // Print this number if it is k-prime if (countPrimeFactors(num) == k) { System.out.print(num + " "); // Increment count of k-primes // printed so far i++; } } return; } /* Driver program to test above function */ public static void main(String[] args) { int n = 10, k = 2; System.out.println("First " + n + " " + k + "-almost prime numbers : "); printKAlmostPrimes(k, n); }}// This code is contributed by vt_m. |
Python3
# Python3 Program to print first # n numbers that are k-primesimport math# A function to count all prime# factors of a given numberdef countPrimeFactors(n): count = 0; # Count the number of # 2s that divide n while(n % 2 == 0): n = n / 2; count += 1; # n must be odd at this point. # So we can skip one # element (Note i = i +2) i = 3; while(i <= math.sqrt(n)): # While i divides n, # count i and divide n while (n % i == 0): n = n / i; count += 1; i = i + 2; # This condition is to handle # the case when n is a # prime number greater than 2 if (n > 2): count += 1; return(count);# A function to print the # first n numbers that are# k-almost primes.def printKAlmostPrimes(k, n): i = 1; num = 2 while(i <= n): # Print this number if # it is k-prime if (countPrimeFactors(num) == k): print(num, end = ""); print(" ", end = ""); # Increment count of # k-primes printed # so far i += 1; num += 1; return;# Driver Coden = 10; k = 2;print("First n k-almost prime numbers:");printKAlmostPrimes(k, n);# This code is contributed by mits |
C#
// C# Program to print first n // numbers that are k-primes using System;class GFG { // A function to count all prime // factors of a given number static int countPrimeFactors(int n) { int count = 0; // Count the number of 2s that divide n while (n % 2 == 0) { n = n / 2; count++; } // n must be odd at this point. So we // can skip one element (Note i = i +2) for (int i = 3; i <= Math.Sqrt(n); i = i + 2) { // While i divides n, count i and // divide n while (n % i == 0) { n = n / i; count++; } } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) count++; return (count); } // A function to print the first n // numbers that are k-almost primes. static void printKAlmostPrimes(int k, int n) { for (int i = 1, num = 2; i <= n; num++) { // Print this number if it is k-prime if (countPrimeFactors(num) == k) { Console.Write(num + " "); // Increment count of k-primes // printed so far i++; } } return; } // Driver code public static void Main() { int n = 10, k = 2; Console.WriteLine("First " + n + " " + k + "-almost prime numbers : "); printKAlmostPrimes(k, n); }}// This code is contributed by Nitin Mittal. |
PHP
<?php// PHP Program to print first // n numbers that are k-primes// A function to count all prime// factors of a given numberfunction countPrimeFactors($n){ $count = 0; // Count the number of // 2s that divide n while($n % 2 == 0) { $n = $n / 2; $count++; } // n must be odd at this point. // So we can skip one // element (Note i = i +2) for ($i = 3; $i <= sqrt($n); $i = $i + 2) { // While i divides n, // count i and divide n while ($n % $i == 0) { $n = $n/$i; $count++; } } // This condition is to handle // the case when n is a // prime number greater than 2 if ($n > 2) $count++; return($count);}// A function to print the // first n numbers that are// k-almost primes.function printKAlmostPrimes($k, $n){ for ($i = 1, $num = 2; $i <= $n; $num++) { // Print this number if // it is k-prime if (countPrimeFactors($num) == $k) { echo($num); echo(" "); // Increment count of // k-primes printed // so far $i++; } } return;} // Driver Code $n = 10; $k = 2; echo "First $n $k-almost prime numbers:\n"; printKAlmostPrimes($k, $n);// This code is contributed by nitin mittal. ?> |
Javascript
<script>// Javascript program to print first n numbers that// are k-primes // A function to count all prime factors // of a given number function countPrimeFactors(n) { let count = 0; // Count the number of 2s that divide n while (n % 2 == 0) { n = n / 2; count++; } // n must be odd at this point. So we // can skip one element (Note i = i +2) for (let i = 3; i <= Math.sqrt(n); i = i + 2) { // While i divides n, count i and // divide n while (n % i == 0) { n = n / i; count++; } } // This condition is to handle the case // when n is a prime number greater // than 2 if (n > 2) count++; return (count); } // A function to print the first n numbers // that are k-almost primes. function printKAlmostPrimes(k, n) { for (let i = 1, num = 2; i <= n; num++) { // Print this number if it is k-prime if (countPrimeFactors(num) == k) { document.write(num + " "); // Increment count of k-primes // printed so far i++; } } return; }// Driver Code let n = 10, k = 2; document.write("First " + n + " " + k + "-almost prime numbers : " + "<br/>"); printKAlmostPrimes(k, n); </script> |
Output
First 10 2-almost prime numbers : 4 6 9 10 14 15 21 22 25 26
Time Complexity: O(sqrt(n))
Auxiliary Space : O(1)
This article is contributed by Rachit Belwariar. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
