### CodingKnight's blog

By CodingKnight, 4 years ago, 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. Comments (0)