Разбор

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

Число называется простым, если оно не имеет других делителей кроме единицы и самого себя.

Теорема. Если число $n$ составное, то оно обязательно имеет делитель, не больший $n$ .

Доказательство. Пусть $n$ составное и $d$ его делитель. Тогда $n / d$ также будет делителем числа $n$ . Если предположить, что все делители числа $n$ больше $n$ , то $d > n$ и $n / d > n$ . Откуда $d * (n / d) > n * n$ или $n > n$ , что является противоречием.

Для проверки числа $n$ на простоту достаточно проверить, делится ли оно на одно из чисел от 2 до $n$ включительно. Если $n$ делится хотя бы на одно их них, то $n$ составное. Иначе простое.

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

Читаем значение $n$ . Установим изначально flag = 1, это означает что $n$ простое.

scanf("%d", &n);
flag = 1;

Перебираем все возможные делители $i$ числа $n$ . Если $n$ делится на $i$ , то оно составное, устанавливаем flag = 0.

for(i = 2; i <= sqrt(n); i++)
    if (n % i == 0)
    {
        flag = 0;
        break;
    }

В зависимости от значения flag выводим ответ.

if (flag == 0) printf("No\n"); else printf("Yes\n");

Реализация алгоритма – через функцию проверки на простоту

#include <stdio.h>
#include <math.h>

int n;

int IsPrime(int n)
{
    for(int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return 0;
    return 1;
}

int main(void)
{
    scanf("%d", &n);
    if (IsPrime(n)) printf("Yes\n"); else printf("No\n");
    return 0;
}

Java реализация

import java.util.*;

public class Main
{
    static boolean IsPrime(int n)
    {
        for(int i = 2; i <= Math.sqrt(n); i++)
            if (n % i == 0) return false;
        return true;
    }

    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int n = con.nextInt();
        if (IsPrime(n))
            System.out.println("Yes");
        else
            System.out.println("No");
        con.close();
    }
}

Python реализация

import math

def IsPrime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0: return False
    return True

n = int(input())
if IsPrime(n):
    print("Yes")
else:
    print("No")