The Last Number Crossed Out by the Sieve
National Olympiad — National round (2019 season)
Submission name: eratosthen.cpp
Problem summary
Process the sieve’s primes and their multiples in increasing order, never crossing a number twice. Find the last newly crossed composite without storing n entries.
Input
n.
Output
The last newly crossed-out number.
Constraints
4 ≤ n ≤ 10^9.
Worked example
Input and output for the worked example discussed below.
Input
10
Output
9
Solution analysis
- A composite is first crossed by its smallest prime factor. Therefore the final active prime p is the largest prime at most sqrt(n): p² exists, while any larger smallest factor would force the composite above n.
- At p’s stage candidates are p×q for p≤q≤floor(n/p). Such a candidate survives earlier stages exactly when q has no prime divisor below p. Mark multiples of all smaller primes in this small cofactor range.
- Scan down for the largest unmarked q. For n=10, p=q=3 gives 9. For n=8, p=2,q=4 gives 8, showing q need not be prime.
- Sieve only to sqrt(n) to obtain p. Bertrand’s prime bound gives floor(n/p)=O(sqrt(n)), so the second sieve also has only a square-root-sized range.
Why it works
Multiples p×q survive to the final sieve stage exactly when q has no smaller prime factor; the largest surviving multiple is crossed last.
Complexity: O(sqrt(n) log log n) time and O(sqrt(n)) space.
Watch out. Mark cofactor multiples from the smaller prime itself, not its square. Do not assume q is prime or allocate a billion-entry sieve.
Commented C++17 solution
An independently written complete program with standard headers.
// Multiples p×q survive to the final sieve stage exactly when q has no smaller prime factor; the largest
// surviving multiple is crossed last.
#include<cmath>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int limit;
cin>>limit;
int root=int(sqrt(limit));
vector<bool>composite(root+1);
vector<int>primes;
for(int value=2;value<=root;value++){
if(!composite[value]){
primes.push_back(value);
for(long long multiple=1LL*value*value;multiple<=root;multiple+=value){
composite[multiple]=true;
}
}
}
int lastPrime=primes.back();
int bound=limit/lastPrime;
vector<bool>blocked(bound+1);
for(int prime:primes){
if(prime==lastPrime){
break;
}
for(int multiple=prime;multiple<=bound;multiple+=prime){
blocked[multiple]=true;
}
}
int cofactor=bound;
while(blocked[cofactor]){
cofactor--;
}
cout<<lastPrime*cofactor<<'\n';
}