Un número k-casi primo es un número que tiene exactamente k factores primos (no necesariamente distintos).
por ejemplo ,
2, 3, 5, 7, 11….(de hecho, todos los números primos) son 1-Números casi primos ya que solo tienen 1 factor primo (que son ellos mismos).
4, 6, 9…. son 2-Números casi primos ya que tienen exactamente 2 factores primos (4 = 2*2, 6 = 2*3, 9 = 3*3)
De manera similar, 32 es un 5-Número casi primo (32 = 2*2*2 *2*2) y también lo es 72 (2*2*2*3*3)
Todos los 1-Casi primos se denominan números primos y todos los 2-Casi primos se denominan semiprimos.
La tarea es imprimir los primeros n números que son k primos.
Ejemplos:
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.
Iteramos los números naturales y seguimos imprimiendo k-primos hasta que el recuento de k-primos impresos sea menor o igual que n. Para verificar si un número es k-primo, encontramos el conteo de factores primos y si el conteo es k, consideramos el número como k-primo.
A continuación se muestra la implementación del enfoque anterior:
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 number
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 <= 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-primes
import 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-primes
import math
# A function to count all prime
# factors of a given number
def 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 Code
n = 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 number
function 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>
Producción
First 10 2-almost prime numbers : 4 6 9 10 14 15 21 22 25 26
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA