CodingKnight's blog

By CodingKnight, 4 years ago, In English

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.

 
 
 
 
  • Vote: I like it
  • -48
  • Vote: I do not like it