Author: Medha Pandey
Tester: Akansha Bigasia
Editorialist: Akansha Bigasia
Maths and Number Theory
We need to figure the exact time by calculating the product of at least three ‘stand numbers’ mentioned on the stairs of the quidditch playground stands.
The problem is asking for first 1000 numbers having distinct prime divisors greater than equal to 3.
There are several methods to find distinct prime division.
By trial division.
Here is the simple solution using trial divisor to find the distinct prime factors, discussed after short explanation.
This task can be done using a simple implementation . Just find all the primes, for numbers by multiplying 3 primes and then for each numbed found , multiply it again with the same primes we used from the beginning, and then when we got a list, we can sort it and we are ready to read the input and output the answer right away. But first for doing this we need to make sure that for n=1000 the number needed won’t be too great.
The primes are:
2,3,5,7,11,13,17,19,23,29,31,37,41.Our initial numbers are going to be made by multiplying 3 different primes. It is not hard to notice that the 1000th number is not going to be formed with a greater number than 41.
So we can be sure that a simple brute force solution will pass the time limit easily.
AUTHOR’S AND TESTER’S SOLUTIONS:
The solution can be found here.