PROBLEM LINK:
Author: Medha Pandey
Tester: Akansha Bigasia
Editorialist: Akansha Bigasia
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Maths and Number Theory
PROBLEM:
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.
QUICK EXPLANATION:
The problem is asking for first 1000 numbers having distinct prime divisors greater than equal to 3.
EXPLANATION:
There are several methods to find distinct prime division.
-
Using sieve
-
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.