Найменший дільник (Розбір)

Переберемо всі можливі дільники числа $n$ в діапазоні від $2$ до \sqrt{n} включно і знайдемо мінімальний. Якщо дільників в інтервалі [2; \sqrt{n}] не виявиться, то відповіддю буде саме число $n$.

Приклад

Якщо n = 21, то найменшим дільником буде $3$.

Якщо n = 13 (просте число), то найменшим дільником буде $13$.

Реалізація алгоритму

Читаємо вхідне число $n$.

scanf("%d", &n);

Ініціалізуємо flag = 0. Перебираємо можливі дільники числа $n$ в діапазоні від $2$ до \sqrt{n} включно. При знаходженні першого (найменшого) дільника встановлюємо flag = 1, виводимо знайдений дільник і завершуємо виконання циклу.

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

Якщо дільник не був знайдений, то число $n$ є простим. У цьому випадку виводимо саме число $n$.

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

Java реалізація

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 реалізація

import math

Читаємо вхідне число $n$.

n = int(input())

Перебираємо можливі дільники числа $n$ в діапазоні від $2$ до \sqrt{n} включно. При знаходженні першого (найменшого) дільника виводимо його і завершуємо виконання циклу.

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

Якщо цикл завершується природним чином (без використання break), то виконується блок else).

Якщо дільник не був знайдений, то число $n$ є простим. Виводимо саме число $n$.

else: # сюди потрапимо коли цикл закінчиться сам
  print(n)