1642. Hometask

 

Kolya is still trying to pass a test on Numbers Theory. The lecturer is so desperate about Kolya’s knowledge that she gives him the same task every time.

The problem is to check if n! is divisible by n2.

 

Input. One integer n (1 ≤ n ≤ 109).

 

Output. Print “YES” if n! is divisible by n2, otherwise print “NO”.

 

Sample input

Sample output

3

NO

 

 

SOLUTION

prime test

 

Algorithm analysis

Since n! = 1 * 2 * … * n, then n! Is divisible by n. If n is prime, the product n! / n  = 1 * 2 * … * (n – 1) is not divisible by n. Therefore, for a prime n, the value of n! is not divisible by n2.

If n is not prime, it can be represented as a product of two numbers (not necessarily prime): for example, n = a * b. Then n! = (a * b)! contains factors a, b, a * b and n! is divisible by n2.

Consider two cases separately:

·        for n = 1 (neither prime nor composite) the value of n! is divisible by n2;

·        for n = 4 (composite) the value of n! is not divisible by n2.

 

Example

If n = 5 (prime), then 5! = 1 * 2 * 3 * 4 * 5 is not divisible by 52.

If n = 15 (composite), then 15! In its factorization contains the multiples 3, 5 and 15, and therefore is divisible by 152.

If n = 4 (composite), then 4! = 1 * 2 * 3* 4 is divisible by 4, but is not divisible by 42.

 

Algorithm realization

Function IsPrime checks if n is prime. If n is prime, function returns 1. Otherwise function returns 0.

 

int IsPrime(int n)

{

  for(int i = 2; i <= sqrt(1.0*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);

 

Print the answer depending on the value of n.

 

if (n == 4) puts("NO"); else

if (n == 1 || !IsPrime(n)) puts("YES");

                      else puts("NO");

 

Java realization

 

import java.util.*;

 

public class Main

{

  public 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 (n == 4) System.out.println("NO"); else

    if (n == 1 || !IsPrime(n)) System.out.println("YES");

    else System.out.println("NO");

    con.close();

  }

}

 

Python realization

 

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 n == 4:

  print("NO")

elif n == 1 or not IsPrime(n):

  print("YES")

else:

  print("NO");