cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2011 · MediumPrime sieve

Super Primes with Prime Decimal Prefixes

National Olympiad — National round (2011 season)

Submission name: super.cpp

Solve in Editor →

Problem summary

Print primes in [a,b] for which repeatedly deleting the final digit leaves primes, except that the final one-digit prefix may also be 1. Number 1 itself is not prime.

Input

a and b.

Output

Qualifying numbers in increasing order, one per line; print NO if none exist.

Constraints

0 < a < b < 10^7.

Worked example

Input and output for the worked example discussed below.

Input

20 50

Output

23
29
31
37

Solution analysis

  1. Precompute primality up to b using Eratosthenes’ sieve. Start composite marking at p²: smaller multiples of p already have a smaller prime factor.
  2. For every prime candidate in the interval, divide its prefix by 10 repeatedly. Every prefix of at least two digits must be prime, and the final single digit must be prime or 1. The full number still must be prime, so 1 never qualifies.
  3. Between 20 and 50, primes 23 and 29 begin with 2, while 31 and 37 begin with 3; all pass. Prime 41 fails because its remaining digit is 4. Prime 11 does qualify through the special final-prefix allowance for 1.

Why it works

The sieve correctly identifies all primes. The prefix loop checks exactly each number obtained by removing one or more rightmost digits, with the specified exception only at the last single digit. Thus a candidate is accepted exactly when it satisfies the definition.

Complexity: O(b log log b + (b−a+1) log b) time and O(b) bits for vector<bool>; each tested prefix chain has at most seven digits.

Watch out. Do not accept 1 as a result, and do not reject 11 merely because its last remaining prefix is 1. The interval endpoints are inclusive.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int left;
    int right;
    cin>>left>>right;
    vector<bool>prime(right+1,true);
    prime[0]=false;
    prime[1]=false;
    for(int factor=2;factor*factor<=right;factor++){
        if(prime[factor]){
            for(int multiple=factor*factor;multiple<=right;multiple+=factor){
                prime[multiple]=false;
            }
        }
    }
    bool found=false;
    for(int value=left;value<=right;value++){
        if(!prime[value]){
            continue;
        }
        int prefix=value/10;
        bool valid=true;
        // Only the final one-digit prefix receives the special allowance for 1.
        while(prefix>0){
            if(!prime[prefix]&&prefix!=1){
                valid=false;
            }
            prefix/=10;
        }
        if(valid){
            found=true;
            cout<<value<<'\n';
        }
    }
    if(!found){
        cout<<"NO\n";
    }
}

Source: Arena Olimpiici ↗