Given x,y, How to find whether x! is divisible by y or not?

Question

computing x! can be very costly and might often result in overflow. Is there a way to find out whether x! is divisible by y or not without computing x!?

• For y < x, its trivial;
• But,for y > x, e.g. x = 5 and y = 60; I am struggling to find a way without computing x!

Answer 1

Compute the prime factorization of x! and y. You can do this without computing x! by factorizing every number from 2 to x and collecting all of the factors together. If the factors of y is a subset of the factors of x! then it is divisible.