Title link

Difficulty: Medium

Title

For any positive integer x, the number of its divisors is written as g(x), such as g(1)=1, g(6)=4.

If a positive integer x satisfies: for any positive integer i less than x, there is g(x)>g(i), then x is called an inverse prime number.

For example, the integers 1, 2, 4, 6, etc. are all inverse primes.

Now given a number N, request the largest inverse prime number not exceeding N.

Input format

A positive integer N.

Output format

An integer representing the largest antiprime number not exceeding N.

Data Range

1≤N≤2∗10^9

Sample input:

1000

Sample output:

840

Prefix knowledge

Unique Decomposition Theorem (Basic Theorem of Arithmetic): Any natural number N greater than 1 can be uniquely decomposed into the product of finite prime numbers

In the Fundamental Theorem of Arithmetic, if a positive integer N is uniquely decomposed into N = , where ci are all positive integers, pi are all prime numbers, and satisfy p1

{}, where 0 ≤ bi ≤ ci

The number of positive divisors of N is (Π represents the symbol of continuous product, similar to ∑):

(c1 + 1) * (c2 + 1) *...* (cm + 1) =

The sum of all positive divisors of N is:

Solution ideas

The inhomogeneity factor of an inverse prime number will not exceed 10, because 2*3*5*7*11*13*17*19*23*29*31>2*10^9 all prime factors of an inverse prime numberThe sum of the exponents does not exceed 30, because 2^31>2*10^9.Therefore, you can use recursive DFS to violently search for all possible combinations of the exponents of the first ten prime numbers. When searching, the exponents should be monotonically decreasing, the total product should not exceed N, and the number of current divisors should be recorded at the same time..

There are two very important properties for antiprimes

Prime factor 𝑝1, 𝑝2, …, 𝑝𝑟 is a continuous prime number starting from 2

Exponentially decreasing prime factors 𝑒1 ≥ 𝑒2 ≥ 𝑒3 … ≥ 𝑒r

Code Example

#include#include#include#include#includeusing namespace std;#define int long longint ps[]={2,3,5,7,11,13,17,19,23,29};int n;int sum,minn;void dfs(int pos, int last, int p, int s){if(s>sum||(s==sum&&pn) break;p*=ps[pos];dfs(pos+1,i,p,s*(i+1));}}signed main(){cin>>n;dfs(0,30,1,1);cout<