Dado un número N, imprima todos los números en el rango de 1 a N que tengan exactamente 3 divisores.
Ejemplos:
Input : N = 16 Output : 4 9 4 and 9 have exactly three divisors. Divisor Input : N = 49 Output : 4 9 25 49 4, 9, 25 and 49 have exactly three divisors.
Después de observar de cerca los ejemplos mencionados anteriormente, notó que todos los números requeridos son cuadrados perfectos y que también son solo números primos. La lógica detrás de esto es que tales números pueden tener solo tres números como su divisor y también eso incluye 1 y ese número en sí mismo resulta en un solo divisor que no es un número, por lo que podemos concluir fácilmente que se requieren esos números que son cuadrados de números primos para que solo puedan tener tres divisores (1, el propio número y sqrt(número)). Entonces todos los primos i, tales que i*i es menor que igual a N son tres números primos.
Nota: Podemos generar todos los números primos dentro de un conjunto usando cualquier método de tamiz de manera eficiente y luego deberíamos todos los números primos i, de modo que i*i <=N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all
// three-primes smaller than
// or equal to n using Sieve
// of Eratosthenes
#include <bits/stdc++.h>
using namespace std;
// Generates all primes upto n and
// prints their squares
void numbersWith3Divisors(int n)
{
bool prime[n+1];
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = 0;
for (int p = 2; p*p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (int i = p*2; i <= n; i += p)
prime[i] = false;
}
}
// print squares of primes upto n.
cout << "Numbers with 3 divisors :\n";
for (int i=0; i*i <= n ; i++)
if (prime[i])
cout << i*i << " ";
}
// Driver program
int main()
{
// sieve();
int n = 96;
numbersWith3Divisors(n);
return 0;
}
Java
// Java program to print all
// three-primes smaller than
// or equal to n using Sieve
// of Eratosthenes
import java.io.*;
import java.util.*;
class GFG
{
// Generates all primes upto n
// and prints their squares
static void numbersWith3Divisors(int n)
{
boolean[] prime = new boolean[n+1];
Arrays.fill(prime, true);
prime[0] = prime[1] = false;
for (int p = 2; p*p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (int i=p*2; i<=n; i += p)
prime[i] = false;
}
}
// print squares of primes upto n
System.out.println("Numbers with 3 divisors : ");
for (int i=0; i*i <= n ; i++)
if (prime[i])
System.out.print(i*i + " ");
}
// Driver program
public static void main (String[] args)
{
int n = 96;
numbersWith3Divisors(n);
}
}
// Contributed by Pramod Kumar
Python3
# Python3 program to print
# all three-primes smaller than
# or equal to n using Sieve
# of Eratosthenes
# Generates all primes upto n
# and prints their squares
def numbersWith3Divisors(n):
prime=[True]*(n+1);
prime[0] = prime[1] = False;
p=2;
while (p*p <= n):
# If prime[p] is not changed,
# then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p*2,n+1,p):
prime[i] = False;
p+=1;
# print squares of primes upto n.
print("Numbers with 3 divisors :");
i=0;
while (i*i <= n):
if (prime[i]):
print(i*i,end=" ");
i+=1;
# Driver program
n = 96;
numbersWith3Divisors(n);
# This code is contributed by mits
C#
// C# program to print all
// three-primes smaller than
// or equal to n using Sieve
// of Eratosthenes
class GFG
{
// Generates all primes upto n
// and prints their squares
static void numbersWith3Divisors(int n)
{
bool[] prime = new bool[n+1];
prime[0] = prime[1] = true;
for (int p = 2; p*p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == false)
{
// Update all multiples of p
for (int i = p*2; i <= n; i += p)
prime[i] = true;
}
}
// print squares of primes upto n
System.Console.WriteLine("Numbers with 3 divisors : ");
for (int i=0; i*i <= n ; i++)
if (!prime[i])
System.Console.Write(i*i + " ");
}
// Driver program
public static void Main()
{
int n = 96;
numbersWith3Divisors(n);
}
}
// This code is Contributed by mits
PHP
<?php
// PHP program to print all three-primes
// smaller than or equal to n using Sieve
// of Eratosthenes
// Generates all primes upto n and
// prints their squares
function numbersWith3Divisors($n)
{
$prime = array_fill(0, $n + 1, true);
$prime[0] = $prime[1] = false;
for ($p = 2; $p * $p <= $n; $p++)
{
// If prime[p] is not changed,
// then it is a prime
if ($prime[$p] == true)
{
// Update all multiples of p
for ($i = $p * 2; $i <= $n; $i += $p)
$prime[$i] = false;
}
}
// print squares of primes upto n.
echo "Numbers with 3 divisors :\n";
for ($i = 0; $i * $i <= $n ; $i++)
if ($prime[$i])
echo $i * $i . " ";
}
// Driver Code
$n = 96;
numbersWith3Divisors($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to print all
// three-primes smaller than
// or equal to n using Sieve
// of Eratosthenes
// Generates all primes upto n and
// prints their squares
function numbersWith3Divisors(n)
{
let prime = new Array(n+1);
prime.fill(true);
prime[0] = prime[1] = 0;
for (let p = 2; p*p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (let i = p*2; i <= n; i += p)
prime[i] = false;
}
}
// print squares of primes upto n.
document.write("Numbers with 3 divisors :" + "</br>");
for (let i = 0; i*i <= n ; i++)
if (prime[i])
document.write(i*i + " ");
}
// sieve();
let n = 96;
numbersWith3Divisors(n);
// This code is contributed by mukesh07.
</script>
Producción:
Numbers with 3 divisors : 4 9 25 49
Complejidad del tiempo : O(sqrt(n))
Espacio Auxiliar : O(n)
Otro enfoque:
Para imprimir todos los números en el rango de 1 a N que tienen exactamente 3 divisores, el cálculo principal es encontrar aquellos que son cuadrados de números primos y menores o iguales que el número. Podemos hacer esto de la siguiente manera:
- Inicie un bucle para el entero i de 2 a n.
- Compruebe si i es primo o no, lo que se puede hacer fácilmente usando el método isPrime(n) .
- Si i es primo, verifica si su cuadrado es menor o igual que el número dado. Esto se comprobará solo para los cuadrados de los números primos, por lo que se reducirá el número de comprobaciones.
- Si se cumple la condición anterior, se imprimirá el número y el bucle continuará hasta i<=n.
De esta manera, no se requerirá espacio adicional para almacenar nada.
Aquí hay una implementación de la lógica anterior sin usar espacio adicional;
C++
// C++ program to print all
// three-primes smaller than
// or equal to n without using
// extra space
#include <bits/stdc++.h>
using namespace std;
void numbersWith3Divisors(int);
bool isPrime(int);
// Generates all primes upto n and
// prints their squares
void numbersWith3Divisors(int n)
{
cout << "Numbers with 3 divisors : "
<< endl;
for(int i = 2; i * i <= n; i++)
{
// Check prime
if (isPrime(i))
{
if (i * i <= n)
{
// Print numbers in
// the order of
// occurrence
cout << i * i << " ";
}
}
}
}
// Check if a number is prime or not
bool isPrime(int n)
{
for(int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Driver code
int main()
{
int n = 122;
numbersWith3Divisors(n);
return 0;
}
// This code is contributed by vishu2908
Java
// Java program to print all
// three-primes smaller than
// or equal to n without using
// extra space
import java.util.*;
class GFG
{
// 3 divisor logic implementation
// check if a number is
// prime or not
// if it is a prime then
// check if its square
// is less than or equal to
// the given number
static void numbersWith3Divisors(int n)
{
System.out.println("Numbers with 3 divisors : ");
for (int i = 2; i * i <= n; i++)
{
// Check prime
if (isPrime(i))
{
if (i * i <= n)
{
// Print numbers in
// the order of
// occurrence
System.out.print(i * i + " ");
}
}
}
}
// Check if a number is prime or not
public static boolean isPrime(int n)
{
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Driver program
public static void main(String[] args)
{
int n = 122;
numbersWith3Divisors(n);
}
}
// Contributed by Parag Pallav Singh
Python3
# Python3 program to print all
# three-primes smaller than
# or equal to n without using
# extra space
# 3 divisor logic implementation
# check if a number is prime or
# not if it is a prime then check
# if its square is less than or
# equal to the given number
def numbersWith3Divisors(n):
print("Numbers with 3 divisors : ")
i = 2
while i * i <= n:
# Check prime
if (isPrime(i)):
if (i * i <= n):
# Print numbers in the order
# of occurrence
print(i * i, end = " ")
i += 1
# Check if a number is prime or not
def isPrime(n):
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
# Driver code
n = 122
numbersWith3Divisors(n)
# This code is contributed by divyesh072019
C#
// C# program to print all
// three-primes smaller than
// or equal to n without using
// extra space
using System;
class GFG{
// 3 divisor logic implementation
// check if a number is prime or
// not if it is a prime then check
// if its square is less than or
// equal to the given number
static void numbersWith3Divisors(int n)
{
Console.WriteLine("Numbers with 3 divisors : ");
for(int i = 2; i * i <= n; i++)
{
// Check prime
if (isPrime(i))
{
if (i * i <= n)
{
// Print numbers in the order
// of occurrence
Console.Write(i * i + " ");
}
}
}
}
// Check if a number is prime or not
public static bool isPrime(int n)
{
for(int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Driver code
static void Main()
{
int n = 122;
numbersWith3Divisors(n);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to print all
// three-primes smaller than
// or equal to n without using
// extra space
// 3 divisor logic implementation
// check if a number is prime or
// not if it is a prime then check
// if its square is less than or
// equal to the given number
function numbersWith3Divisors(n)
{
document.write("Numbers with 3 divisors : ");
for(let i = 2; i * i <= n; i++)
{
// Check prime
if (isPrime(i))
{
if (i * i <= n)
{
// Print numbers in the order
// of occurrence
document.write(i * i + " ");
}
}
}
}
// Check if a number is prime or not
function isPrime(n)
{
if (n == 0 || n == 1)
return false;
for(let i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
let n = 122;
numbersWith3Divisors(n);
// This code is contributed by suresh07.
</script>
Producción:
Numbers with 3 divisors : 4 9 25 49 121
Complejidad de tiempo: O(sqrtN 2 )
Espacio Auxiliar: O(1)
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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