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

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

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

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

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

РЕШЕНИЕ

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

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

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

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

Доказательство. Пусть n – составное число и d – его делитель. Тогда n / d также является делителем числа n. Предположим, что все делители числа n больше . Тогда одновременно выполняются неравенства d > и n / d > . Умножив эти неравенства, получаем:

d * (n / d) > * ,

то есть n > n. Это приводит к противоречию. Таким образом, если число n составное, то хотя бы один из его делителей не превышает .

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

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

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

scanf("%d",&n);

Установим флаг flag = 1. Это означает, что n предположительно является простым.

flag = 1;

Перебираем все возможные делители i числа n от 2 до включительно. Если n делится на i, то n является составным, поэтому устанавливаем 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");

Реализация алгоритма – функция

Функция IsPrime проверяет, является ли число n простым.

int IsPrime(int n)

{

for (int i = 2; i <= sqrt(n); i++)

if (n % i == 0) return 0;

return 1;

}

Основная часть программы. Читаем входное значение n.

scanf("%d",&n);

В зависимости от простоты числа n выводим ответ.

if (IsPrime(n)) printf("Yes\n");

else printf("No\n");

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

Функция IsPrime проверяет, является ли число n простым.

def IsPrime(n):

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

if n % i == 0: return False

return True

Основная часть программы. Читаем входное значение n.

n = int(input())

В зависимости от простоты числа n выводим ответ.

if IsPrime(n):

print("Yes")

else:

print("No")