Different Divisors (Codeforces 1474B)
Tags: Greedy, number theory

Positive integer $$$x$$$ is called divisor of positive integer $$$y$$$, if $$$y$$$ is divisible by $$$x$$$ without remainder. For example, $$$1$$$ is a divisor of $$$7$$$ and $$$3$$$ is not divisor of $$$8$$$.We gave you an integer $$$d$$$ and asked you to find the smallest positive integer $$$a$$$, such that  $$$a$$$ has at least $$$4$$$ divisors;  difference between any two divisors of $$$a$$$ is at least $$$d$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3000$$$) — the number of test cases.The first line of each test case contains a single integer $$$d$$$ ($$$1 \leq d \leq 10000$$$).

Output: For each test case print one integer $$$a$$$ — the answer for this test case.

Note: In the first test case, integer $$$6$$$ have following divisors: $$$[1, 2, 3, 6]$$$. There are $$$4$$$ of them and the difference between any two of them is at least $$$1$$$. There is no smaller integer with at least $$$4$$$ divisors.In the second test case, integer $$$15$$$ have following divisors: $$$[1, 3, 5, 15]$$$. There are $$$4$$$ of them and the difference between any two of them is at least $$$2$$$.The answer $$$12$$$ is INVALID because divisors are $$$[1, 2, 3, 4, 6, 12]$$$. And the difference between, for example, divisors $$$2$$$ and $$$3$$$ is less than $$$d=2$$$.

Sample Inputs:
2
1
2

Sample Outputs:
6
15

Solution (Python):
import sys

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    prime_numbers = [i for i in range(n + 1) if primes[i]]
    return prime_numbers

def find_greater_or_equal(numbers, target):
    left = 0
    right = len(numbers) - 1
    result = None
    while left <= right:
        mid = left + (right - left) // 2
        if numbers[mid] >= target:
            result = numbers[mid]
            right = mid - 1
        else:
            left = mid + 1
    return result
ls = sieve_of_eratosthenes(25000)
t = int(sys.stdin.readline().strip())
for _ in range(t):
    d = int(sys.stdin.readline().strip())
    a = 1 + d
    x = find_greater_or_equal(ls, a)
    a = x
    b = a + d
    x = find_greater_or_equal(ls, b)
    b = x
    sys.stdout.write(str(a * b) + '\n')

Solution (Python):
a = [1] * 8 ** 5
i = 2
while (b := ([0] * -(-8 ** 5 // i + i))):
    a[i * i::i] = b
    i += 1
for s in [*open(0)][1:]:
    d = int(s)
    i = a.index(1, d + 1)
    print(i * a.index(1, i + d))

Solution (Python):
N = 8 ** 5
a = [1] * N
i = 2
while i * i < N:
    a[i * i::i] = [0] * -(-N // i + i)
    i += 1
for s in [*open(0)][1:]:
    d = int(s)
    i = a.index(1, d + 1)
    print(i * a.index(1, i + d))