Factorial division

[yabi2943993]

I want to see, if the factorial of a number n is divisible by a number p.
For that I got:

#include <iostream>
int main() {
    int p,n;
    while(1){
    std::cin>>p;
    std::cin>>n;
    if(p<0 && n<0){break;}else{
    int fact=n;
     while(n>=2){
            fact*=(n-1);
            n--; }
    
    if(fact%p==0){std::cout<<"YES"<<"\n";}
    else{std::cout<<"NO"<<"\n";}}}
	return 0;
}

Maybe is there a more efiicient way to make such program?
Thanks

[kbw]

You don't have to calculate F(n), then do the check.

If F(3) is divisible by p, then so is F(4); because F(4) = 4 * F(3).

Please don't post duplicates.
http://www.cplusplus.com/forum/general/267527/

[yabi2943993]

How could I transform that into code?

[dutch]

Stop posting in both forums.

How could I transform that into code?

Borrow a functioning brain?

[jonnin]

hmm, how in the world would we know if 120! is divisible by 121... or 119...
one of those you know already. the second takes a min or 2 of thinking it through. what do you know about 120! vs 119?
what do you know about 121?
This is 100% basic math, and 0% code. The only exotic thing you might need to know about c++ is that it contains a GCD already, and you don't even need that (but it may be one approach).

Here is a question to get you started: how many times can you divide 120! by 11 evenly?

[againtry]

n! on my calculator is easy. Trouble is it hasn’t got a p button.

[kbw]

The way to check if one number is divisible by another is to check if the modulus is zero. The modulus happens to be the remainder in a division.

In code that looks like:

#include <iostream>

int main() {
    int a = 4, b = 3;
    int remainder = a % b;
    if (remainder == 0)
        std::cout << a << " is divisible by " << b << "\n"; 
    else
        std::cout << a << " is not divisible by " << b << "\n"; 
}

You should be posting in the Beginners forum rather than here.

[jonnin]

But its not the best way here, because he does not have the integers he wants to resolve in hand, he has to compute one of them (his way).

take my example. is 120! divisible by 121 or not? Yes, it is. why?
1*2*3... *11... *22...*33...*44... so 11*11, 121, will go into 120!, without the need for a huge int class to store 120! or a loop to compute it.

so what the question is, is this ... prime factor (with repeats!!) the number you want to check (in my example, the PF of 121 is 11*11) and then ask "are there 2 copies of 11 in 120!"

you can resolve this for a rather large factorial and divisor without needing to deal with the huge factorial.

If it were only asking about small factorials and you had a lookup table of them all, say all that will fit in u64 type, then % would be the way to do it. Given that he is talking TLE that means 'codechef' to me and that means 'they probably asking about big factorials'.

Of course, now he has to write a prime factor algorithm!
If you want to beat the clock, lookup tables where you can and don't answer the same question twice (eg if asked to compute 5! and then 10!, start with 5! that you already found).

[yabi2943993]

Just found a solution for this problem. I didn't understand very well the examples you were trying to show me. Actually I discovered, that every p is divisible by the factorial of n if p=n or p=1.
Result code:

#include <iostream>
int main(){
    int p,n;
    std::cin>>p>>n;
    while(p>=0 || n>=0){
        if(p<=n || p==1){std::cout<<"YES"<<"\n";}
        else{std::cout<<"NO"<<"\n";}
        std::cin>>p>>n;
    }return 0;}

[dutch]

yikes!

[dutch]

So nobody has any quibbles with this solution?

[jonnin]

He reversed the problem.

I want to see, if the factorial of a number n is divisible by a number p.

Actually I discovered, that every p is divisible by the factorial of n if p=n or p=1.

Not knowing what the question is anymore, I can't say much about his answer. If he is happy, I am happy.

[dutch]

Not only did he reverse the problem but he then states that "p is divisible by the factorial of n if p=n or p=1", which is patently false (e.g., is 5 divisible by 5! = 5*4*3*2*1?).

Then he implements something different (and still not true) like this:
if (p <= n || p == 1) std::cout << "YES\n";

Going back to the original problem statement, obviously n! is divisible by p if p is in [1, n], but that doesn't cover all the cases since, for example, 5! is also divisible by 20.

Still, he seems content. :)

[jonnin]

reminds me of a fight about performance... "yours is 5x slower than mine"... "yes but yours gives the wrong answer... if you are ok with the wrong answer, I can give you that instantly".