Números menores que N que son producto de exactamente dos números primos distintos

Posted on by Rudeus Greyrat

Dado un número  norte . La tarea es encontrar todos esos números menores que N y son un producto de exactamente dos números primos distintos. 
Por ejemplo, 33 es el producto de dos números primos distintos, es decir, 11 * 3, mientras que números como 60 tienen tres factores primos distintos, es decir, 2 * 2 * 3 * 5.
Nota : estos números no pueden ser un cuadrado perfecto.
Ejemplos: 
 

Entrada : N = 30 
Salida : 6, 10, 14, 15, 21, 22, 26
Entrada : N = 50 
Salida : 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39 , 46 
 

Algoritmo : 
 

  1. Recorra hasta N y verifique si cada número tiene exactamente dos factores primos o no.
  2. Ahora, para evitar la situación como 49 que tiene 7 * 7 producto de dos números primos, verifica si el número es un cuadrado perfecto o no para asegurarte de que tiene dos primos distintos.
  3. Si el Paso 1 y el Paso 2 satisfacen, agregue el número en la lista de vectores.
  4. Atraviesa el vector e imprime todos los elementos en él.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find numbers that are product
// of exactly two distinct prime numbers
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether a number
// is a PerfectSquare or not
bool isPerfectSquare(long double x)
{
 
    long double sr = sqrt(x);
 
    return ((sr - floor(sr)) == 0);
}
 
// Function to check if a number is a
// product of exactly two distinct primes
bool isProduct(int num)
{
    int cnt = 0;
 
    for (int i = 2; cnt < 2 && i * i <= num; ++i) {
        while (num % i == 0) {
            num /= i;
            ++cnt;
        }
    }
 
    if (num > 1)
        ++cnt;
 
    return cnt == 2;
}
 
// Function to find numbers that are product
// of exactly two distinct prime numbers.
void findNumbers(int N)
{
    // Vector to store such numbers
    vector<int> vec;
 
    for (int i = 1; i <= N; i++) {
        if (isProduct(i) && !isPerfectSquare(i)) {
 
            // insert in the vector
            vec.push_back(i);
        }
    }
 
    // Print all numbers till n from the vector
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
}
 
// Driver function
int main()
{
    int N = 30;
 
    findNumbers(N);
 
    return 0;
}

Java

// Java program to find numbers that are product
// of exactly two distinct prime numbers
import java.util.*; 
 
class GFG{
// Function to check whether a number
// is a PerfectSquare or not
static boolean isPerfectSquare(double x)
{
 
    double sr = Math.sqrt(x);
 
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function to check if a number is a
// product of exactly two distinct primes
static boolean isProduct(int num)
{
    int cnt = 0;
 
    for (int i = 2; cnt < 2 && i * i <= num; ++i) {
        while (num % i == 0) {
            num /= i;
            ++cnt;
        }
    }
 
    if (num > 1)
        ++cnt;
 
    return cnt == 2;
}
 
// Function to find numbers that are product
// of exactly two distinct prime numbers.
static void findNumbers(int N)
{
    // Vector to store such numbers
    Vector<Integer> vec = new Vector<Integer>();
 
    for (int i = 1; i <= N; i++) {
        if (isProduct(i) && !isPerfectSquare(i)) {
 
            // insert in the vector
            vec.add(i);
        }
    }
 
    // Print all numbers till n from the vector
    Iterator<Integer> itr = vec.iterator(); 
            while(itr.hasNext()){ 
                 System.out.print(itr.next()+" "); 
            } 
}
 
// Driver function
public static void main(String[] args)
{
    int N = 30;
 
    findNumbers(N);
}
}
// This Code is Contributed by mits

Python 3

# Python 3 program to find numbers that are product
# of exactly two distinct prime numbers
 
import math
# Function to check whether a number
# is a PerfectSquare or not
def isPerfectSquare(x):
  
    sr = math.sqrt(x)
  
    return ((sr - math.floor(sr)) == 0)
 
# Function to check if a number is a
# product of exactly two distinct primes
def isProduct( num):
    cnt = 0
  
    i = 2
    while cnt < 2 and i * i <= num:
        while (num % i == 0) :
            num //= i
            cnt += 1
        i += 1
  
    if (num > 1):
        cnt += 1
  
    return cnt == 2
  
# Function to find numbers that are product
# of exactly two distinct prime numbers.
def findNumbers(N):
    # Vector to store such numbers
    vec = []
  
    for i in range(1,N+1) :
        if (isProduct(i) and not isPerfectSquare(i)) :
  
            # insert in the vector
            vec.append(i)
  
    # Print all numbers till n from the vector
    for i in range(len( vec)):
        print(vec[i] ,end= " ")
  
# Driver function
if __name__=="__main__":
     
    N = 30
    findNumbers(N)

C#

// C# program to find numbers that are product
// of exactly two distinct prime numbers
using System;
using System.Collections.Generic;
 
class GFG
{
    // Function to check whether a number
    // is a PerfectSquare or not
    static bool isPerfectSquare(double x)
    {
 
        double sr = Math.Sqrt(x);
 
        return ((sr - Math.Floor(sr)) == 0);
    }
 
    // Function to check if a number is a
    // product of exactly two distinct primes
    static bool isProduct(int num)
    {
        int cnt = 0;
 
        for (int i = 2; cnt < 2 && i * i <= num; ++i)
        {
            while (num % i == 0)
            {
                num /= i;
                ++cnt;
            }
        }
 
        if (num > 1)
            ++cnt;
 
        return cnt == 2;
    }
 
    // Function to find numbers that are product
    // of exactly two distinct prime numbers.
    static void findNumbers(int N)
    {
        // Vector to store such numbers
        List<int> vec = new List<int>();
 
        for (int i = 1; i <= N; i++)
        {
            if (isProduct(i) && !isPerfectSquare(i))
            {
 
                // insert in the vector
                vec.Add(i);
            }
        }
 
        // Print all numbers till n from the vector
        foreach(var a in vec)
                    Console.Write(a + " ");
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int N = 30;
 
        findNumbers(N);
    }
}
 
// This code has been contributed by 29AjayKumar

PHP

<?php
// PHP program to find numbers that are product
// of exactly two distinct prime numbers
 
// Function to check whether a number
// is a PerfectSquare or not
function isPerfectSquare($x)
{
    $sr = sqrt($x);
 
    return (($sr - floor($sr)) == 0);
}
 
// Function to check if a number is a
// product of exactly two distinct primes
function isProduct($num)
{
    $cnt = 0;
 
    for ($i = 2; $cnt < 2 &&
         $i * $i <= $num; ++$i)
    {
        while ($num % $i == 0)
        {
            $num /= $i;
            ++$cnt;
        }
    }
 
    if ($num > 1)
        ++$cnt;
 
    return $cnt == 2;
}
 
// Function to find numbers that are product
// of exactly two distinct prime numbers.
function findNumbers($N)
{
    // Vector to store such numbers
    $vec = array();
 
    for ($i = 1; $i <= $N; $i++)
    {
        if (isProduct($i) &&
           !isPerfectSquare($i))
        {
 
            // insert in the vector
            array_push($vec, $i);
        }
    }
 
    // Print all numbers till n from the vector
    for ($i = 0; $i < sizeof($vec); $i++)
    {
        echo $vec[$i] . " ";
    }
}
 
// Driver Code
$N = 30;
 
findNumbers($N);
 
// This code is contributed by ita_c

Javascript

<script>
 
// Javascript program to find numbers that are product
// of exactly two distinct prime numbers
 
// Function to check whether a number
// is a PerfectSquare or not
function isPerfectSquare(x)
{
    sr = Math.sqrt(x);
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function to check if a number is a
// product of exactly two distinct primes
function isProduct(num)
{
    var cnt = 0;
 
    for(var i = 2; cnt < 2 && (i * i) <= num; ++i)
    {
        while (num % i == 0)
        {
            num = parseInt(num / i);
            ++cnt;
        }
    }
 
    if (num > 1)
        ++cnt;
 
    return cnt == 2;
}
 
// Function to find numbers that are product
// of exactly two distinct prime numbers.
function findNumbers( N)
{
    // Vector to store such numbers
    vec = [];
 
    for (var i = 1; i <= N; i++)
    {
        if (isProduct(i) && !isPerfectSquare(i))
        {
 
            // insert in the vector
            vec.push(i);
        }
    }
 
    // Print all numbers till n from the vector
    for (var i = 0; i < vec.length; i++) {
        document.write(vec[i] + " ");
    }
}
 
// Driver function
var N = 30;
findNumbers(N);
 
// This code is contributed by noob2000.
</script>
Producción: 

6 10 14 15 21 22 26

 

Complejidad temporal: O( norte * $\sqrt{n}$ )
 Espacio auxiliar: O(n) 

Publicación traducida automáticamente

Artículo escrito por Shashank_Pathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *