1616. Простое ли число?

Проверьте, является ли заданное число простым. Простым называется такое число, которое имеет не более двух делителей: 1 и само число.

Вход. Одно натуральное 32-х битовое знаковое число n.

Выход. Выведите “Yes” если число простое, и “No” в противном случае.

Пример входа	Пример выхода
5	Yes

РЕШЕНИЕ

тест на простоту

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

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

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

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

Для проверки числа n на простоту достаточно проверить, делится ли оно на одно из чисел от 2 до включительно. Если 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")