Чи є число простим?#1616

Чи є число простим? (Розбір)

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

Теорема. Якщо число $n$ складене, то воно обов'язково має дільник, що не перевищує $n$ \sqrt{n}.

Доказ. Нехай $n$ — складене число і $d$ — його дільник. Тоді $n / d$ також є дільником числа $n$ . Припустимо, що всі дільники числа $n$ більші за $n$ \sqrt{n}. Тоді одночасно виконуються нерівності $d > n$ d > \sqrt{n} і $n / d > n$ n / d > \sqrt{n}. Помноживши ці нерівності, отримуємо:

d * (n / d) > n * n,

d * (n / d) > \sqrt{n} * \sqrt{n},

тобто $n > n$ n > n. Це призводить до протиріччя. Таким чином, якщо число $n$ складене, то принаймні один з його дільників не перевищує $n$ \sqrt{n}.

Для перевірки числа $n$ на простоту достатньо перевірити, чи ділиться воно на одне з чисел від $2$ до $n$ \sqrt{n} включно. Якщо $n$ ділиться принаймні на одне з цих чисел, то $n$ є складеним. В іншому випадку $n$ просте.

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

Зчитуємо вхідне значення $n$ .

scanf("%d",&n);

Встановимо прапор $f l a g = 1$ flag = 1. Це означає, що $n$ ймовірно є простим.

flag = 1;

Перебираємо всі можливі дільники $i$ числа $n$ від $2$ до $n$ \sqrt{n} включно. Якщо $n$ ділиться на $i$ , то $n$ є складеним, тому встановлюємо $f l a g = 0$ flag = 0.

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

Залежно від значення $f l a g$ виводимо відповідь.

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();
  }
}

Java

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")