The following is C++17 data structure primes_t for the simple Sieve of Eratosthenes algorithm that features:

1. Constructor primes_t( int M, int N ) that computes all prime numbers in the interval [M,N], and stores those ordered prime numbers in an inherited vector< int > base class.

2. Member function bool exists( int x ) that uses binary search to find whether or not x exists among prime numbers in the specified interval.

3. Inheriting all public member functions of vector< int > as public members functions of primes_t.

#include <bits/stdc++.h>

using namespace std;

struct primes_t: vector< int >
{
    primes_t( int M, int N )
    {
        int p = 3, x = 0, z = ( N - 1 ) / 2; bool composite_odd[ z ];

        for( int x1 = 0; x1 < z; x1++ )
            composite_odd[ x1 ] = false;

        if ( M <= 2 && N >= 2 )
            push_back( 2 );

        for( int q = sqrt( N ); p <= q; p += 2, x++ )
            if ( !composite_odd[ x ] )
            {
                if ( p >= M )
                  push_back( p );

                for( int x1 = p * x + 3 * ( x + 1 ), y1 = p * p; y1 <= N; x1 += p, y1 += 2 * p )
                    composite_odd[ x1 ] = true;
            }

        do
        {
            if ( !composite_odd[ x ] && p >= M )
                push_back( p );

             p += 2, x++;
        }
        while( p <= N );
    }

    bool exists( int x ) const 
    { 
        return binary_search( cbegin(), cend(), x ); 
    }
};

For example, the following program computes and prints the count of prime numbers in the interval [M,N].

int main()
{
    int M, N;

    cin >> M >> N;

    cout << primes_t( M, N ).size();
}

The data structure can be used by Codeforces as any other shared library in the public domain.

Thank you.

The following is the Prolog help page on the Kattis Problems Archive.

https://open.kattis.com/help/prolog

Kattis uses the free SWI-Prolog compiler to judge solutions implemented in Prolog. It may be useful that Codeforces team considers adopting this approach for including Prolog among the programming languages which can be used in Codeforces Rounds and Educational Contests.

The ISO International Standard ISO/IEC 14882:2017(E) – Programming Language C++, known as C++17, is the result of excellent efforts by the ISO C++ Standard Foundation Committee to introduce new simple and elegant powerful features to C++.

Adrian D. Finlay, Software Engineer, summarized on Nov 17, 2017, the new C++17 language features that are helpful to competitive programming lovers as well as to professional software engineers and software developers as follows.

"The never-ending journey into learning C++ features….

New Language Features

1. Addition of __has_include macro

2. UTF 8 Character Literals

3. Hexadecimal Floating Point Literals

4. New rules for deduction of single member list using auto

5. Update to __cplusplus value

6. inline variables

7. New Syntax for Nested Namespace definitions

8. Initializers added to if/switch statements

9. constexpr if

10. New standard attributes fallthrough, maybe_unused &nodiscard ^

11. Attributes for Enumerator & Namespaces

12. Error message for static_assert now optional

13. Structured binding declarations

14. Keyword typename now allowed in lieu of class in a template’s template paramater

15. Constant evaluation for non-type template arguments

16. Class template argument deduction

17. Extensions on over-aligned Memory Allocation

18. Fold expressions

19. List-style Initialization of Enumerations

20. Specifying non-type template parameters with auto

21. constexpr lambda expressions

22. Lambda this by value (*this)

23. Extending Aggregate Initialization to Base Types

24. Unknown Attributes Required to be Ignored

25. Pack Expansions legal in using declarations

26. Generalization of Range-based for loop

27. The byte data type ^^

28. Using attribute namespaces without repetition

29. Stricter Order of Evaluation Rules

30. Exception Specifications are part of type definitions

31. Template-Template Parameters match compatible arguments

32. Guaranteed Copy Elision

33. Changes to Specification on Inheriting Constructors

^These are three features grouped into one, which consequently when expanded would make the new feature list count 35.

^^This is implemented in std::byte () and is not a part of the actual language such as the other primitive data types. It is considered a basic type as much as std::string is considered a basic type.

C++17 also introduced a revision to Elementary string conversions".

The Complete Blog posted on Medium.com

Stephan Roth, Clean C++ Sustainable Software Development Patterns and Best Practices with C++17, Apress, 2017.

Please refer to the 6th question and its answer in the following Codeforces blog:

Frequently Asked Questions

Best wishes

The Integral Image

The following declares a C++ class template int_set< int From, int To > that uses bitset STL to compute operations on sets of integers using bitset STL bitwise operators. int_set< int From, int To > is a class of objects that represent subsets of universal domain U = [ From, To ].

Each object stores the membership function of the corresponding subset using a private bitset<N> member exists, where N = ( To - From + 1 ), and can be updated using set insertion/deletion operations.

The main advantage of int_set< int From, int To > is that the set insertion/deletion operations as well as the fundamental set union, intersection, complement, difference, and symmetric difference operations are implemented using the standard C++ bitset STL bitwise operators, unlike the corresponding set STL operations that require adding/deleting elements to/from the binary tree representation of the set, which improves the performance of those operations.

int_set.h and sample test program

The following are C++11 classes huge_unsigned and binomial_coefficient for computing huge Binomial coefficients C( n, k ), where n and k are positive integers.

The class implements the iterative multiplicative formula:

def binomialCoefficient(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k) # take advantage of symmetry
    c = 1
    for i in range(k):
        c = c * (n - i) / (i + 1)
    return c

reported in Binomial coefficient without overflow, and without using the modulus arithmetic operator. Items of the STL base class vector< uint32_t > are used to store the successive digits of a base-4,294,967,296 representation of C( n, k ). C( 32000, 16000 ) has been computed using 1000 huge_unsigned digits in 1.873 sec. on Intel Core i3 processor with 3 GB RAM running at 2.4 GHz. Comments and votes (like or do not like) are thankfully and gratefully appreciated.

#include <bits/stdc++.h>

using namespace std;

struct huge_unsigned: public vector< uint32_t >
{
    uint64_t carry;

    huge_unsigned() : carry( 0 ) {}

    huge_unsigned& operator *= ( uint32_t i )
    {
        register uint64_t p, q, x = i; 

        for( register size_t k = 0, l = size(); k < l; at( k++ ) = q, carry = ( q >> 32 ) )
        {
            p = at( k ), q = p * x;

            if ( carry != 0 )
                q += carry;
        }

         if ( carry != 0 )
            push_back( carry ), carry = 0;

        return *this;
    }

    huge_unsigned& operator /= ( uint32_t j )
    {
        register uint64_t p, q, x = j;

        for ( register size_t k = size(); k > 0; at( k ) = q, carry = p - q * x )
            p = ( carry << 32 ) | at( --k ), q = p / x;

        while( size() > 0 && back() == 0 )
            pop_back();

        return *this;
    }

    void write()
    {
        for( register size_t k = size() - 1; k > 0; k-- )
            printf( "%u ", at( k ) );

        printf( "%u", at( 0 ) );
    }
};

struct binomial_coefficient: public huge_unsigned
{
    binomial_coefficient( uint32_t n, uint32_t k )
    {
        if ( k > n )
        {
            push_back( 0 ); return;
        }

        register uint32_t p = n - k, q = min( k, p );

        if ( q == 0 )
        {
            push_back( 1 ); return;
        }

        push_back( n-- );

        for( register uint32_t i = 2; i <= q; *this /= i++ )
            *this *= n--;
    }
};

int main() // A sample test program
{
    uint32_t n, k; scanf( "%u %u", &n, &k );

    clock_t start_time = clock();

    binomial_coefficient c( n, k );

    clock_t end_time = clock();

    double elapsed_time = ( end_time - start_time ) * 1000.0 / CLOCKS_PER_SEC;

    printf( "Computed c( %u, %u ) = ", n, k ), c.write(), putchar( '\n' ),
    printf( "Using %u huge unsigned digits(s)\n", c.size() ),
    printf( "Elapsed time = %f msec.\n", elapsed_time );
}