Dado un número N, encuentre el divisor primo más pequeño de N.
Ejemplos:
Entrada: 25
Salida: 5Entrada: 31
Salida: 31
Acercarse:
- Comprueba si el número es divisible por 2 o no.
- Iterar de i = 3 a sqrt(N) y dando un salto de 2.
- Si alguno de los números divide a N, entonces es el divisor primo más pequeño.
- Si ninguno de ellos divide, entonces N es la respuesta.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ program to count the number of // subarrays that having 1 #include <bits/stdc++.h> using namespace std; // Function to find the smallest divisor int smallestDivisor(int n) { // if divisible by 2 if (n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return i; } return n; } // Driver Code int main() { int n = 31; cout << smallestDivisor(n); return 0; }
Java
// Java program to count the number of // subarrays that having 1 import java.io.*; class GFG { // Function to find the smallest divisor static int smallestDivisor(int n) { // if divisible by 2 if (n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return i; } return n; } // Driver Code public static void main (String[] args) { int n = 31; System.out.println (smallestDivisor(n)); } }
Python3
# Python3 program to count the number # of subarrays that having 1 # Function to find the smallest divisor def smallestDivisor(n): # if divisible by 2 if (n % 2 == 0): return 2; # iterate from 3 to sqrt(n) i = 3; while(i * i <= n): if (n % i == 0): return i; i += 2; return n; # Driver Code n = 31; print(smallestDivisor(n)); # This code is contributed by mits
C#
// C# program to count the number // of subarrays that having 1 using System; class GFG { // Function to find the // smallest divisor static int smallestDivisor(int n) { // if divisible by 2 if (n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return i; } return n; } // Driver Code static public void Main () { int n = 31; Console.WriteLine(smallestDivisor(n)); } } // This code is contributed // by Sach_Code
PHP
<?php // PHP program to count the number // of subarrays that having 1 // Function to find the smallest divisor function smallestDivisor($n) { // if divisible by 2 if ($n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for ($i = 3; $i * $i <= $n; $i += 2) { if ($n % $i == 0) return $i; } return $n; } // Driver Code $n = 31; echo smallestDivisor($n); // This code is contributed by Sachin ?>
Javascript
<script> // javascript program to count the number of // subarrays that having 1 // Function to find the smallest divisor function smallestDivisor(n) { // if divisible by 2 if (n % 2 == 0) return 2; // iterate from 3 to sqrt(n) for (var i = 3; i * i <= n; i += 2) { if (n % i == 0) return i; } return n; } // Driver Code var n = 31; document.write(smallestDivisor(n)); // This code is contributed by todaysgaurav </script>
Producción:
31
¿Cómo encontrar eficientemente los factores primos de todos los números hasta n?
Consulte el factor mínimo primo de números hasta n
Complejidad de tiempo: O (sqrt (N)), ya que estamos usando un ciclo para atravesar sqrt (N) veces. Como la condición es i*i<=N, al aplicar la función sqrt en ambos lados obtenemos sqrt (i*i) <= sqrt(N), que es i<= sqrt(N), por lo tanto, el ciclo atravesará para sqrt(N) veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.