Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
math::prime_sieve::SegmentedSieve Class Reference

#include <segmented_sieve.h>

List of all members.

Static Public Member Functions

static void findPrimes (long long int n, SieveCallback *callback)

Static Private Member Functions

static void sieve (const vector< int > &primes, long long int segment_start, long long int delta, long long int n, SieveCallback *callback)

Detailed Description

Implementation of segmented sieve

The basic idea is to a) find all primes up to sqrt(n) (inclusive) b) sieve sucessive intervals of length sqrt(n)

  • each interval can be sieved in the same way as in normal sieve, we just need to maintain for each prime[i] position L[i] of last crossed-out number

Member Function Documentation

static void math::prime_sieve::SegmentedSieve::findPrimes ( long long int  n,
SieveCallback callback 
) [inline, static]

Find all primes less than n and report them to the supplied callback

Parameters:
n
callbackuse this callback on each found prime
static void math::prime_sieve::SegmentedSieve::sieve ( const vector< int > &  primes,
long long int  segment_start,
long long int  delta,
long long int  n,
SieveCallback callback 
) [inline, static, private]

Interval sieving


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines