El divisor primo más pequeño de un número

Dado un número N, encuentre el divisor primo más pequeño de N. 

Ejemplos: 

Entrada: 25 
Salida: 5

Entrada: 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++ 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  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 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# 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 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
?>

<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>

31

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.