Найменший дільник (#8927)

Аналіз алгоритму

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

Приклад

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

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

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

scanf("%d", &n);

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

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

Якщо дільник не був знайдений, то число $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 = int(input())

for i in range(2, math.isqrt(n)+1):
    if n % i == 0:
        print(i)
        break
else: # сюди потрапимо коли цикл закінчиться сам
    print(n)