Smallest divisor (Editorial)

Iterate through all possible divisors of $n$ in the range from $2$ to \sqrt{n} inclusive and find the smallest one. If no divisors are found in the interval [2; \sqrt{n}], the answer will be the number $n$ itself.

Example

If n = 21, the smallest divisor is $3$.

If n = 13 (a prime number), the smallest divisor is $13$.

Algorithm implementation

Read the input value of $n$.

scanf("%d", &n);

Initialize flag = 0. Iterate through the possible divisors of $n$ in the range from $2$ to \sqrt{n} inclusive. Upon finding the first (smallest) divisor, set flag = 1, print the found divisor, and terminate 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 is found, the number $n$ is prime. In this case, print the number $n$ itself.

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

Read the input value of $n$.

n = int(input())

Iterate through the possible divisors of $n$ in the range from $2$ to \sqrt{n} inclusive. Upon finding the first (smallest) divisor, print it and terminate the loop.

for i in range(2, math.isqrt(n)+1):
  if n % i == 0:
    print(i)
    break

If the loop terminates naturally (without using break), the else block is executed.

If no divisor is found, the number $n$ is prime. Print the number $n$ itself.

else: # we are here when the loop terminates by itself
  print(n)