Розбір

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

Число називається простим, якщо воно не має інших дільників крім одиниці та самого себе.

Теорема. Якщо число $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")