CareerCup

How can they ask such question in interviews. Its something very weird and i doubt it to be an interview question.

the prime_no between 31 to 3000000 will be one of the multiple in 3000000! / 30!
for prime_no <=30; 30*prime_number will be one of the multiple in 3000000! / 30!

power by 100000 will not change the divisibility

so
if (prime_no <= 3000000) return 0 ;
else return prime_no;

If you knew Lucas' theorem, then you could solve this easily.

The number is nothing but

(3000000 choose (3000000 - 30)) * ((3000000 - 30) choose (3000000 - 60)) * ( (3000000 - 60) choose (3000000 - 90)) ....

Each binomial coefficient can be computed modulo the prime p using Lucas's theorem (which involves writing the numbers in base p).

If you don't know Lucas' theorem, perhaps you can try and do some clever cancellations to simplify it...

It is always 0.

Say the prime number is P.

There are two cases

1) P>30
in this case P will be present in (3000000!)/(30!) so (3000000!)/(30) % P will be zero(^10000 does not matter)

2) P < 30
for any prime number P (which is less than 30) there will be at least one number X such that X%P=0 && X>30 .(for P=5..X=35 and for P=7 ...X=49....etc) even in this case ((3000000!)/(30!)) %P will be 0 because of the presence of X.

so in any case the answer is zero

ppo thayoli

(3,000,000)0