Factovisors

Time limit1sMemory limit128 MB

Summary
For each pair n and m, decide whether m divides n! by comparing the prime factors of m against those of n!.
Level

Medium5 of 10

Topics
Number theory, Math
Solved
No attempts yet

Problem

For a non-negative integer nn, the factorial function n!n! is defined as follows:

0! = 1
n! = n * (n-1)!   (n > 0)

We say that aa divides bb if there exists an integer kk such that k×a=bk \times a = b.

Given two non-negative integers nn and mm, determine whether mm divides n!n!.

Input

The input consists of several lines. Each line contains two non-negative integers nn and mm, separated by a space, both less than 2312^{31}. Input continues until the end of the file (EOF).

Output

For each input line, print m divides n! if mm divides n!n!, and m does not divide n! otherwise, on its own line. Replace m and n with the actual values from the input.

Examples1

  1. Example 1

    Input
    6 9
6 27
20 10000
20 100000
1000 1009
    Expected output
    9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!