Dado un número N(1<=N<=10 9 ), la tarea es encontrar el número total de enteros menores que n que tienen exactamente 9 divisores.
Ejemplos:
Entrada: N = 100
Salida: 2
Los dos números que tienen exactamente 9 divisores son 36 y 100.
Entrada: N = 1000
Salida: 8
Los números son 36 100 196 225 256 441 484 676
Un enfoque ingenuo es iterar todos los números hasta N y contar los números que tienen exactamente 9 divisores. Para contar el número de divisores, uno puede iterar fácilmente hasta N y comprobar si N es divisible por i o no y llevar la cuenta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count factors in O(N)
int numberOfDivisors(int num)
{
int c = 0;
// iterate and check if factor or not
for (int i = 1; i <= num; i++) {
if (num % i == 0) {
c += 1;
}
}
return c;
}
// Function to count numbers having
// exactly 9 divisors
int countNumbers(int n)
{
int c = 0;
// check for all numbers <=N
for (int i = 1; i <= n; i++) {
// check if exactly 9 factors or not
if (numberOfDivisors(i) == 9)
c += 1;
}
return c;
}
// Driver Code
int main()
{
int n = 1000;
cout << countNumbers(n);
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
class GFG {
// Function to count factors in O(N)
static int numberOfDivisors(int num)
{
int c = 0;
// iterate and check if factor or not
for (int i = 1; i <= num; i++) {
if (num % i == 0) {
c += 1;
}
}
return c;
}
// Function to count numbers having
// exactly 9 divisors
static int countNumbers(int n)
{
int c = 0;
// check for all numbers <=N
for (int i = 1; i <= n; i++) {
// check if exactly 9 factors or not
if (numberOfDivisors(i) == 9)
c += 1;
}
return c;
}
// Driver Code
public static void main (String[] args) {
int n = 1000;
System.out.print(countNumbers(n));
}
}
// This code is contributed by inder_verma..
Python 3
# Python 3 implementation of # above approach # Function to count factors in O(N) def numberOfDivisors(num): c = 0 # iterate and check if # factor or not for i in range(1, num + 1) : if (num % i == 0) : c += 1 return c # Function to count numbers having # exactly 9 divisors def countNumbers(n): c = 0 # check for all numbers <=N for i in range(1, n + 1) : # check if exactly 9 factors or not if (numberOfDivisors(i) == 9): c += 1 return c # Driver Code if __name__ == "__main__": n = 1000 print(countNumbers(n)) # This code is contributed # by ChitraNayal
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to count factors in O(N)
static int numberOfDivisors(int num)
{
int c = 0;
// iterate and check if factor or not
for (int i = 1; i <= num; i++)
{
if (num % i == 0)
{
c += 1;
}
}
return c;
}
// Function to count numbers having
// exactly 9 divisors
static int countNumbers(int n)
{
int c = 0;
// check for all numbers <=N
for (int i = 1; i <= n; i++) {
// check if exactly 9 factors or not
if (numberOfDivisors(i) == 9)
c += 1;
}
return c;
}
// Driver Code
public static void Main ()
{
int n = 1000;
Console.Write(countNumbers(n));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP implementation of above approach
// Function to count factors in O(N)
Function numberOfDivisors($num)
{
$c = 0;
// iterate and check
// if factor or not
for ($i = 1; $i <= $num; $i++) {
if ($num % $i == 0) {
$c += 1;
}
}
return $c;
}
// Function to count numbers
// having exactly 9 divisors
Function countNumbers($n)
{
$c = 0;
// check for all numbers <=N
for ($i = 1; $i <= $n; $i++) {
// check if exactly 9 factors or not
if (numberOfDivisors($i) == 9)
$c += 1;
}
return $c;
}
// Driver Code
$n = 1000;
echo countNumbers($n);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to count factors in O(N)
function numberOfDivisors(num)
{
let c = 0;
// iterate and check if factor or not
for (let i = 1; i <= num; i++)
{
if (num % i == 0)
{
c += 1;
}
}
return c;
}
// Function to count numbers having
// exactly 9 divisors
function countNumbers(n)
{
let c = 0;
// check for all numbers <=N
for (let i = 1; i <= n; i++) {
// check if exactly 9 factors or not
if (numberOfDivisors(i) == 9)
c += 1;
}
return c;
}
let n = 1000;
document.write(countNumbers(n));
</script>
Producción:
8
Complejidad de tiempo: O(N 2 ), ya que estamos usando un ciclo para recorrer N veces y en cada recorrido estamos llamando a la función número deDivisores que costará O (N) en el peor de los casos, por lo que la complejidad del programa será O( N*N).
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Un enfoque eficiente es usar la propiedad del factor primo para contar el número de divisores de un número. El método se puede encontrar aquí . Si cualquier número (sea x) se puede expresar en términos de (p^2 * q^2) o (p^8), donde p y q son factores primos de X, entonces X tiene un total de 9 divisores. Los siguientes pasos se pueden seguir para resolver el problema anterior.
- Usa la técnica Sieve para marcar el factor primo más pequeño de un número.
- Solo necesitamos verificar todos los números en el rango [1-sqrt(n)] que se pueden expresar en términos de p*q ya que (p^2*q^2) tiene 9 factores, por lo tanto, (p*q) ^2 también tendrá exactamente 9 factores.
- Iterar de 1 a sqrt(n) y verificar si i se puede expresar como p*q , donde p y q son números primos.
- Además, verifique si i es primo, entonces pow(i, 8)<=n o no, en ese caso, cuente ese número también.
- La suma de la cuenta de números que se pueden expresar en la forma p*q y p^8 es nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count numbers having
// exactly 9 divisors
int countNumbers(int n)
{
int c = 0;
int limit = sqrt(n);
// Sieve array
int prime[limit + 1];
// initially prime[i] = i
for (int i = 1; i <= limit; i++)
prime[i] = i;
// use sieve concept to store the
// first prime factor of every number
for (int i = 2; i * i <= limit; i++) {
if (prime[i] == i) {
// mark all factors of i
for (int j = i * i; j <= limit; j += i)
if (prime[j] == j)
prime[j] = i;
}
}
// check for all numbers if they can be
// expressed in form p*q
for (int i = 2; i <= limit; i++) {
// p prime factor
int p = prime[i];
// q prime factor
int q = prime[i / prime[i]];
// if both prime factors are different
// if p*q<=n and q!=
if (p * q == i && q != 1 && p != q) {
c += 1;
}
else if (prime[i] == i) {
// Check if it can be expressed as p^8
if (pow(i, 8) <= n) {
c += 1;
}
}
}
return c;
}
// Driver Code
int main()
{
int n = 1000;
cout << countNumbers(n);
return 0;
}
Java
// Java implementation of above approach
public class GFG {
// Function to count numbers having
// exactly 9 divisors
static int countNumbers(int n) {
int c = 0;
int limit = (int) Math.sqrt(n);
// Sieve array
int prime[] = new int[limit + 1];
// initially prime[i] = i
for (int i = 1; i <= limit; i++) {
prime[i] = i;
}
// use sieve concept to store the
// first prime factor of every number
for (int i = 2; i * i <= limit; i++) {
if (prime[i] == i) {
// mark all factors of i
for (int j = i * i; j <= limit; j += i) {
if (prime[j] == j) {
prime[j] = i;
}
}
}
}
// check for all numbers if they can be
// expressed in form p*q
for (int i = 2; i <= limit; i++) {
// p prime factor
int p = prime[i];
// q prime factor
int q = prime[i / prime[i]];
// if both prime factors are different
// if p*q<=n and q!=
if (p * q == i && q != 1 && p != q) {
c += 1;
} else if (prime[i] == i) {
// Check if it can be expressed as p^8
if (Math.pow(i, 8) <= n) {
c += 1;
}
}
}
return c;
}
// Driver Code
public static void main(String[] args) {
int n = 1000;
System.out.println(countNumbers(n));
}
}
/*This code is contributed by PrinciRaj1992*/
Python3
# Python3 implementation of the above approach # Function to count numbers # having exactly 9 divisors def countNumbers(n): c = 0 limit = int(n ** (0.5)) # Sieve array, initially prime[i] = i prime = [i for i in range(limit + 1)] # use sieve concept to store the # first prime factor of every number i = 2 while i * i <= limit: if prime[i] == i: # mark all factors of i for j in range(i * i, limit + 1, i): if prime[j] == j: prime[j] = i i += 1 # check for all numbers if they # can be expressed in form p*q for i in range(2, limit + 1): # p prime factor p = prime[i] # q prime factor q = prime[i // prime[i]] # if both prime factors are different # if p*q<=n and q!= if p * q == i and q != 1 and p != q: c += 1 elif prime[i] == i: # Check if it can be # expressed as p^8 if i ** 8 <= n: c += 1 return c # Driver Code if __name__ == "__main__": n = 1000 print(countNumbers(n)) # This code is contributed # by Rituraj Jain
C#
// C# implementation of above approach
using System;
public class GFG {
// Function to count numbers having
// exactly 9 divisors
static int countNumbers(int n) {
int c = 0;
int limit = (int) Math.Sqrt(n);
// Sieve array
int []prime = new int[limit + 1];
// initially prime[i] = i
for (int i = 1; i <= limit; i++) {
prime[i] = i;
}
// use sieve concept to store the
// first prime factor of every number
for (int i = 2; i * i <= limit; i++) {
if (prime[i] == i) {
// mark all factors of i
for (int j = i * i; j <= limit; j += i) {
if (prime[j] == j) {
prime[j] = i;
}
}
}
}
// check for all numbers if they can be
// expressed in form p*q
for (int i = 2; i <= limit; i++) {
// p prime factor
int p = prime[i];
// q prime factor
int q = prime[i / prime[i]];
// if both prime factors are different
// if p*q<=n and q!=
if (p * q == i && q != 1 && p != q) {
c += 1;
} else if (prime[i] == i) {
// Check if it can be expressed as p^8
if (Math.Pow(i, 8) <= n) {
c += 1;
}
}
}
return c;
}
// Driver Code
public static void Main() {
int n = 1000;
Console.WriteLine(countNumbers(n));
}
}
/*This code is contributed by PrinciRaj1992*/
PHP
<?php
// PHP implementation of above approach
// Function to count numbers having
// exactly 9 divisors
function countNumbers($n)
{
$c = 0;
$limit = sqrt($n);
// Sieve array
$prime[$limit + 1] = array(0);
// initially prime[i] = i
for ($i = 1; $i <= $limit; $i++)
$prime[$i] = $i;
// use sieve concept to store the
// first prime factor of every number
for ($i = 2; $i * $i <= $limit; $i++)
{
if ($prime[$i] == $i)
{
// mark all factors of i
for ($j = $i * $i;
$j <= $limit; $j += $i)
if ($prime[$j] == $j)
$prime[$j] = $i;
}
}
// check for all numbers if they
// can be expressed in form p*q
for ($i = 2; $i <= $limit; $i++)
{
// p prime factor
$p = $prime[$i];
// q prime factor
$q = $prime[$i / $prime[$i]];
// if both prime factors are different
// if p*q<=n and q!=
if ($p * $q == $i && $q != 1 && $p != $q)
{
$c += 1;
}
else if ($prime[$i] == $i)
{
// Check if it can be expressed as p^8
if (pow($i, 8) <= $n)
{
$c += 1;
}
}
}
return $c;
}
// Driver Code
$n = 1000;
echo countNumbers($n);
// This code is contributed by jit_t
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to count numbers having
// exactly 9 divisors
function countNumbers(n) {
let c = 0;
let limit = parseInt(Math.sqrt(n), 10);
// Sieve array
let prime = new Array(limit + 1);
prime.fill(0);
// initially prime[i] = i
for (let i = 1; i <= limit; i++) {
prime[i] = i;
}
// use sieve concept to store the
// first prime factor of every number
for (let i = 2; i * i <= limit; i++) {
if (prime[i] == i) {
// mark all factors of i
for (let j = i * i; j <= limit; j += i) {
if (prime[j] == j) {
prime[j] = i;
}
}
}
}
// check for all numbers if they can be
// expressed in form p*q
for (let i = 2; i <= limit; i++) {
// p prime factor
let p = prime[i];
// q prime factor
let q = prime[parseInt(i / prime[i], 10)];
// if both prime factors are different
// if p*q<=n and q!=
if (p * q == i && q != 1 && p != q) {
c += 1;
} else if (prime[i] == i) {
// Check if it can be expressed as p^8
if (Math.pow(i, 8) <= n) {
c += 1;
}
}
}
return c;
}
let n = 1000;
document.write(countNumbers(n));
</script>
Producción:
8
Complejidad de tiempo: O(N), ya que estamos usando bucles anidados en los que el bucle exterior atraviesa sqrt(N) veces y el bucle interior también atraviesa sqrt(N) en el peor de los casos, por lo que la complejidad de tiempo efectiva del programa será O (N)
Espacio auxiliar: O(sqrt(N)), ya que estamos usando espacio adicional para la array principal.