# NUMHUNT - Editorial

Author: just_a_looser1
Tester: mexomerf
Editorialist: iceknight1093

TBD

# PREREQUISITES:

Primality testing in \mathcal{O}(\sqrt X)

# PROBLEM:

You’re given a positive integer X.
Find the smallest positive integer Y that is not prime, not a square, and has no factors smaller than X other than 1.

# EXPLANATION:

We’d like Y to be a non-prime, meaning it must either be a power of a prime, or have at least two different prime factors.

Case 1: Suppose Y is a power of a prime, i.e, Y = p^k for some prime p and non-negative integer k.

• Y shouldn’t be a prime, so k cannot equal 1.
• Y shouldn’t be a square, so k cannot be even.

This means the smallest possible value of k is k = 3, i.e, Y could be the cube of a prime.
Now, p is a prime factor of Y, and so should be \geq X as per our requirement.
Clearly, the best choice is to choose p as the smallest prime that’s \geq X.

Case 2: Suppose Y isn’t a prime power; meaning it has (at least) two distinct prime factors.
Note that we require all the factors of Y to be \geq X, so its prime factors should certainly be \geq X.
Recall that p was already the smallest prime that’s \geq X.
Let’s also find q \gt p as the smallest prime larger than p.
The number Y = p\cdot q is then the smallest number that can be formed as the product of distinct primes not less than X.

Combining the two cases, the answer is simply \min(p^3, p\cdot q) once p and q have been found.

That only leaves the task of actually finding p and q.
Notice that all we really need to do is find the smallest prime that’s \geq a given integer.
That can be done using brute force!

That is, to find the smallest prime p that’s \geq X, the following simple algorithm works:

1. Initialize p = X.
2. While p is not prime, increment p by 1.

Checking whether p is a prime can be done in \mathcal{O}(\sqrt p) time.
Since X \leq 10^9 for us, the this algorithm will check at most 282 values of p before it finds a prime, because the maximal prime gap is quite small.

As an aside, the fact that the prime gap is so small allows for the p^3 case to be discarded entirely - that is, the answer is always the product of the two smallest primes not smaller than X.
Intuitively, this is because q is always not much larger than p, so pq is similar in magnitude to p^2 and so much smaller than p^3.

It can be formally proved (for X upto 10^9) by verifying via bruteforce for smaller values (say, for X \leq 10^5); and utilizing the fact that q \leq p+300 for 10^5 \lt X \leq 10^9.

# TIME COMPLEXITY:

\mathcal{O}(600\sqrt X) per testcase.

# CODE:

Author's code (C++)
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#define int long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;

const int N=500023;
bool vis[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

bool isprime(int x){
if(x==1) return false;
for(int i=2;i*i<=x;i++){
if(x%i==0) return false;
}
return true;
}

void solve()
{
long long ans = 1;
long long first = -1;
long long second = -1;
for(int i = x; second == -1; i++){
if(isprime(i)){
if(first == -1){
first = i;
} else {
second = i;
}
}
}
cerr << first << ' ' << second << '\n';
ans = first*second;
cout << ans;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--){
solve();
cout<<'\n';
}
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool isPrime(int x){
if(x == 1){
return false;
}
for(int i = 2; i * i <= x; i++){
if(x % i == 0){
return false;
}
}
return true;
}
int32_t main() {
int t;
cin>>t;
while(t--){
int x;
cin>>x;
int i = x;
int a = -1;
int b;
while(true){
if(isPrime(i)){
if(a == -1){
a = i;
}else{
b = i;
break;
}
}
i++;
}
cout<<a * b<<"\n";
}
}

Editorialist's code (Python)
def prime(x):
if x == 1: return 0
for p in range(2, x):
if p*p > x: break
if x%p == 0: return 0
return 1

for _ in range(int(input())):
x = int(input())

p = x
while not prime(p): p += 1
q = p+1
while not prime(q): q += 1
print(min(p*q, p**3))

1 Like

I don’t think these kind of questions should appear in the contest. The time complexity was impossible to prove without checking it from oeis. The questions should not ‘require’ participants to use google to solve. I checked the prime gaps, but seeing the constraints of 10^9, I never thought the setter would want us to actually go and calculate the maximum prime gap for prime numbers till that limit. So I kept checking for other methods and gave up until I ‘brute forced’ it and it passed at the last minute.

I didn’t want to be rude, please take this as a feedback. The question didn’t deserve to be at the place with or without the hint that max prime gap till 10^9 is less than 300.

4 Likes

include <bits/stdc++.h>
using namespace std;
bool is_prime(int n ){
if(n==1||n==0)
return false;
if(n==2||n==3)
return true;
for(int i =2; ii<=n ; i++){
if(n %i==0)
return false;
}
return true;
}
int main() {
int t;
cin>>t;
while(t–){
int x;
cin>>x;
long long p = x;
while(!is_prime(p)){
p+=1;
}
long long q= p+1;
while(!is_prime(q)){
q+=1;
}
cout<< min((long long)p
q, (long long)ppp )<<endl;
}

}
would anybody tell what’s wrong in my code

There exists a much faster algorithm for checking Primality. Refer this article on cp-algorithms.com. Using this, you can achieve O(\log(N)^3) per test-case.

1 Like

that is what happend to me as well, i was first thinking along the lines of Seive of eratosthenes, to build up the solution but was getting TLE, then finally i saw that test cases are less than 5 then i tried brute forcing the logic and it passed.

I agree proving this during the contest without any external help feels impossible.

1 Like

Maybe it is, even if I considered primality checking to be O(1), the issue with prime gaps remained. The closest answer that I could get (which is also trivial) was, from Wikipedia:

Bertrand’s postulate, proven in 1852, states that there is always a prime number between k and 2k , so in particular p n +1 < 2p n, which means g n < p n .

From this, the upper bound for next prime could go up to 2 x 10^9, and checking all numbers between 10^9 and 2 x 10^9 is still unfeasible. I am sorry if I have missed something, but it is easy to miss details when problems are not clear enough and thousands of unproved and guesswork submissions ruin the contest.

Check the Wikipedia source shared by the Editorialist.
The 82 known maximal prime gaps.

There it’s mentioned that the maximal prime gap for primes below 10^9 is 282.
The pair of primes with the maximal difference is (436273009, 436273291).

Therefore, this is just an upper bound but the maximal prime gap is still 282 for primes below 10^9. Recheck the constraints and analyse the time complexity.

Cool, the editorialist did not mention the link to the exact table, in my defense. Either way, I don’t believe such questions should appear in contests. The answer should not require participant to use google.

In fact, min(p^3, pq) = pq always.
once p is found, by Bertrand’s postulate there must exist a prime between p and 2p, and such a prime q < 2p < p^2 for all primes p, therefore min(pq, p^3) is always pq