 # STD-Editorial

CONTEST

PRACTICE

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.

1. Using sieve

2. 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.

//