Prime Numbers and Divisors Problem

Problem Representative number-theory task for this round: primes and divisors — e.g. count/list the divisors of n, determine primality for many queries, or count primes below N. (Exact statement varies; master the toolkit.)

Input / Output

• Input: n (or an array of queries up to 10^6+). Output: per the variant — divisor list/count, primality booleans, prime count.

Constraints

• Single n up to 10^12; many queries up to 10^6–10^7.

Example

• n = 36 → divisors {1,2,3,4,6,9,12,18,36} (count 9 = (2+1)(2+1) from 36 = 2²·3²); primes < 10 → 4.