Smallest divisor (#8927)

Algorithm Analysis

We will iterate over the divisors of the number $n$ from 2 to $n$ and output the minimum. If no divisors were found in the interval $[2; n]$ , then the answer will be the number $n$ itself.

Example

If $n = 21$ , then its smallest divisor will be 3.
If $n = 13$ (a prime number), then its smallest divisor will be 13.

Algorithm Implementation

Read the input value $n$ .

scanf("%d", &n);

Set flag = 0. Iterate over the possible divisors from 2 to $n$ . Upon finding the first (smallest) divisor, set flag = 1, output the divisor, and exit the loop.

flag = 0;
for (i = 2; i <= sqrt(n); i++)
    if (n % i == 0)
    {
        printf("%d\n", i);
        flag = 1;
        break;
    }

If no divisor was found, then the number $n$ is prime. Output it.

if (flag == 0)
    printf("%d\n", n);

Java Implementation

import java.util.*;

class Main 
{
    public static void main(String[] args) 
    {
        Scanner con = new Scanner(System.in);
        int n = con.nextInt();
        int flag = 0;
        for (int i = 2; i <= Math.sqrt(n); i++)
            if (n % i == 0)
            {
                System.out.println(i);
                flag = 1;
                break;
            }
        if (flag == 0) System.out.println(n);    
        con.close();
    }
}

Python Implementation

import math

n = int(input())

for i in range(2, math.isqrt(n)+1):
    if n % i == 0:
        print(i)
        break
else: # we will get here when the loop finishes on its own
    print(n)