Editorial

Algorithm Analysis

A number is called prime if it has no other divisors except for one and itself.

Theorem. If a number $n$ is composite, then it must have a divisor not greater than $n$ .

Proof. Suppose $n$ is composite and $d$ is its divisor. Then $n / d$ will also be a divisor of $n$ . If we assume that all divisors of $n$ are greater than $n$ , then $d > n$ and $n / d > n$ . From here $d * (n / d) > n * n$ or $n > n$ , which is a contradiction.

To check if a number $n$ is prime, it is enough to check if it is divisible by any number from 2 to $n$ inclusive. If $n$ is divisible by at least one of them, then $n$ is composite. Otherwise, it is prime.

Algorithm Implementation

Read the value of $n$ . Initially set flag = 1, this means that $n$ is prime.

scanf("%d", &n);
flag = 1;

Iterate over all possible divisors $i$ of the number $n$ . If $n$ is divisible by $i$ , then it is composite, set flag = 0.

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

Depending on the value of flag, output the answer.

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

Implementation of the Algorithm – Through a Prime Checking Function

#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 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

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