Prime number? (Editorial)

A number is called prime if it has no divisors other than $1$ and itself.

Тheorem. If a number $n$ is composite, then it must have a divisor that does not exceed \sqrt{n}.

Proof. Let $n$ be a composite number, and let $d$ be one of its divisors. Then $n/d$ is also a divisor of $n$. Assume that all divisors of $n$ are greater than \sqrt{n}. Then the inequalities d > \sqrt{n} и n / d > \sqrt{n} hold simultaneously. Multiplying these inequalities, we get:

which simplifies to n > n. This is a contradiction. Therefore, if $n$ is composite, at least one of its divisors does not exceed \sqrt{n}.

To check whether a number $n$ is prime, it is sufficient to verify if it is divisible by any number from $2$ to \sqrt{n} inclusive. If $n$ is divisible by at least one of these numbers, then $n$ is composite. Otherwise, $n$ is prime.

Algorithm implementation

Read the input value of $n$.

scanf("%d",&n);

Set the flag flag = 1. This means that $n$ is initially assumed to be a prime number.

flag = 1;

Iterate through all possible divisors $i$ of the number $n$ from $2$ to \sqrt{n} inclusive. If $n$ is divisible by $i$, then $n$ is composite, so set flag = 0.

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

Based on the value of $flag$, print the result.

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

Algorithm implementation — function

The function IsPrime checks whether the number $n$ is prime.

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

The main part of the program. Read the input value of $n$.

scanf("%d",&n);

Based on the primality of the number $n$, print the result.

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

Java implementation

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 implementation

import math

The function IsPrime checks whether the number $n$ is prime.

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

The main part of the program. Read the input value of $n$.

n = int(input())

Based on the primality of the number $n$, print the result.

if IsPrime(n):
  print("Yes")
else:
  print("No")