1616. Prime number?

Check if the given number is a prime number. A number is considered prime if it has exactly two divisors: 1 and the number itself.

Input. One positive signed 32-bit integer n.

Output. Print “Yes” if n is a prime number, and “No” otherwise.

Sample input	Sample output
5	Yes

SOLUTION

prime test

Algorithm analysis

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 .

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. Then the inequalities d > and n / d > hold simultaneously. Multiplying these inequalities, we get:

d * (n / d) > * ,

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

To check whether a number n is prime, it is sufficient to verify if it is divisible by any number from 2 to 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 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")