8927. Наименьший деитель

Для заданного натурального числа n найдите и выведите его наименьший делитель, отличный от 1.

Вход. Одно натуральное число n (1 < n < 2³¹).

Выход. Выведите наименьший делитель числа n, отличный от 1.

Пример входа	Пример выхода
21	3

РЕШЕНИЕ

простые числа

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

Переберем все возможные делители числа n в диапазоне от 2 до включительно и найдем минимальный. Если делителей в интервале [2; ] не обнаружится, то ответом будет само число n.

Пример

Если n = 21, то наименьшим делителем будет 3.

Если n = 13 (простое число), то наименьшим делителем будет 13.

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

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

scanf("%d", &n);

Инициализируем flag = 0. Перебираем возможные делители числа n в диапазоне от 2 до включительно. При нахождении первого (наименьшего) делителя устанавливаем 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 до включительно. При нахождении первого (наименьшего) делителя выводим его и завершаем выполнение цикла.

for i in range(2, math.isqrt(n)+1):

if n % i == 0:

print(i)

break

Если цикл завершается естественным образом (без использования break), то выполняется блок else.

Если делитель не был найден, то число n является простым. Выводим само число n.

else: # сюда попадем когда цикл закончится сам

print(n)