HTML code for sharing Prime Numbers Generator after http://www.rsdn.ru/Forum/?mid=2969898 source code

HTML Copy To Clipboarddone!

<div class="highlight" style="background: #f8f8f8"><pre style="line-height: 125%"><div id="lc1"><span style="color: #BC7A00">#include &lt;memory&gt;</span>
</div><div id="lc2"><span style="color: #BC7A00">#include &lt;math.h&gt;</span>
</div><div id="lc3"><span style="color: #BC7A00">#include &lt;time.h&gt;</span>
</div><div id="lc4"><span style="color: #BC7A00">#include &quot;../generator.h&quot;</span>
</div><div id="lc5">
</div><div id="lc6"><span style="color: #008000; font-weight: bold">typedef</span> <span style="color: #B00040">unsigned</span> word_t;
</div><div id="lc7"><span style="color: #008000; font-weight: bold">const</span> word_t bits_in_word <span style="color: #666666">=</span> <span style="color: #666666">8</span> <span style="color: #666666">*</span> <span style="color: #008000; font-weight: bold">sizeof</span>(word_t);
</div><div id="lc8">
</div><div id="lc9"><span style="color: #008000; font-weight: bold">template</span> <span style="color: #666666">&lt;</span><span style="color: #008000; font-weight: bold">typename</span> Primes<span style="color: #666666">&gt;</span>
</div><div id="lc10"><span style="color: #008000; font-weight: bold">struct</span> gen_map
</div><div id="lc11">{
</div><div id="lc12">    <span style="color: #008000; font-weight: bold">typedef</span> <span style="color: #008000; font-weight: bold">typename</span> Primes<span style="color: #666666">::</span>nat_type nat_type;
</div><div id="lc13">
</div><div id="lc14">    gen_map(nat_type p0, nat_type p1)
</div><div id="lc15">        <span style="color: #666666">:</span> lo_(p0 <span style="color: #666666">*</span> p0)
</div><div id="lc16">        , hi_(p1 <span style="color: #666666">*</span> p1)
</div><div id="lc17">        , bound_((hi_ <span style="color: #666666">-</span> lo_) <span style="color: #666666">/</span> <span style="color: #666666">2</span> <span style="color: #666666">-</span> <span style="color: #666666">1</span>)
</div><div id="lc18">        , arr_(<span style="color: #008000; font-weight: bold">new</span> word_t [bound_ <span style="color: #666666">/</span> bits_in_word <span style="color: #666666">+</span> <span style="color: #666666">1</span>])
</div><div id="lc19">        , i_(<span style="color: #666666">~</span>nat_type(<span style="color: #666666">0</span>))
</div><div id="lc20">        , n_(lo_)
</div><div id="lc21">    {
</div><div id="lc22">        <span style="color: #008000; font-weight: bold">for</span> (word_t i <span style="color: #666666">=</span> <span style="color: #666666">0</span>
</div><div id="lc23">            ; i <span style="color: #666666">!=</span> bound_ <span style="color: #666666">/</span> bits_in_word <span style="color: #666666">+</span> <span style="color: #666666">1</span>
</div><div id="lc24">            ; <span style="color: #666666">++</span>i)
</div><div id="lc25">            arr_[i] <span style="color: #666666">=</span> word_t(<span style="color: #666666">0</span>);
</div><div id="lc26">        Primes ps(<span style="color: #666666">3</span>);
</div><div id="lc27">        <span style="color: #008000; font-weight: bold">for</span> (ps.next(); ps.value() <span style="color: #666666">!=</span> p1; ps.next())
</div><div id="lc28">        {
</div><div id="lc29">            <span style="color: #008000; font-weight: bold">const</span> nat_type i <span style="color: #666666">=</span> ps.value();
</div><div id="lc30">            <span style="color: #008000; font-weight: bold">for</span> (nat_type j <span style="color: #666666">=</span> correct(i <span style="color: #666666">-</span> lo_ <span style="color: #666666">%</span> i, i) <span style="color: #666666">/</span> <span style="color: #666666">2</span> <span style="color: #666666">-</span> <span style="color: #666666">1</span>
</div><div id="lc31">                ; j <span style="color: #666666">&lt;</span> bound_
</div><div id="lc32">                ; j <span style="color: #666666">+=</span> i)
</div><div id="lc33">                arr_[j <span style="color: #666666">/</span> bits_in_word] <span style="color: #666666">|=</span> <span style="color: #666666">1</span> <span style="color: #666666">&lt;&lt;</span> (j <span style="color: #666666">%</span> bits_in_word);
</div><div id="lc34">        }
</div><div id="lc35">        next();
</div><div id="lc36">    }
</div><div id="lc37">
</div><div id="lc38">    <span style="color: #666666">~</span>gen_map()
</div><div id="lc39">    { <span style="color: #008000; font-weight: bold">delete</span>[] arr_; }
</div><div id="lc40">
</div><div id="lc41">    <span style="color: #B00040">bool</span> avail() <span style="color: #008000; font-weight: bold">const</span>
</div><div id="lc42">    { <span style="color: #008000; font-weight: bold">return</span> i_ <span style="color: #666666">!=</span> bound_; }
</div><div id="lc43">
</div><div id="lc44">    nat_type value() <span style="color: #008000; font-weight: bold">const</span>
</div><div id="lc45">    { <span style="color: #008000; font-weight: bold">return</span> n_; }
</div><div id="lc46">
</div><div id="lc47">    <span style="color: #B00040">void</span> next()
</div><div id="lc48">    {
</div><div id="lc49">        <span style="color: #008000; font-weight: bold">do</span> { <span style="color: #666666">++</span>i_; n_ <span style="color: #666666">+=</span> <span style="color: #666666">2</span>; }
</div><div id="lc50">        <span style="color: #008000; font-weight: bold">while</span> (
</div><div id="lc51">            avail() <span style="color: #666666">&amp;&amp;</span>
</div><div id="lc52">            (arr_[i_ <span style="color: #666666">/</span> bits_in_word] <span style="color: #666666">&amp;</span> (<span style="color: #666666">1</span> <span style="color: #666666">&lt;&lt;</span> (i_ <span style="color: #666666">%</span> bits_in_word))));
</div><div id="lc53">    }
</div><div id="lc54">
</div><div id="lc55"><span style="color: #008000; font-weight: bold">private</span><span style="color: #666666">:</span>
</div><div id="lc56">    <span style="color: #008000; font-weight: bold">static</span> nat_type correct(nat_type n, nat_type i)
</div><div id="lc57">    { <span style="color: #008000; font-weight: bold">return</span> n <span style="color: #666666">&amp;</span> <span style="color: #666666">1</span> <span style="color: #666666">?</span> n <span style="color: #666666">+</span> i <span style="color: #666666">:</span> n; }
</div><div id="lc58">
</div><div id="lc59">    <span style="color: #008000; font-weight: bold">const</span> nat_type lo_, hi_, bound_;
</div><div id="lc60">    word_t <span style="color: #666666">*</span>arr_;
</div><div id="lc61">    nat_type i_, n_;
</div><div id="lc62">};
</div><div id="lc63">
</div><div id="lc64"><span style="color: #008000; font-weight: bold">template</span> <span style="color: #666666">&lt;</span><span style="color: #008000; font-weight: bold">typename</span> Natural<span style="color: #666666">&gt;</span>
</div><div id="lc65"><span style="color: #008000; font-weight: bold">inline</span> Natural sqrt_int(Natural x)
</div><div id="lc66">{ <span style="color: #008000; font-weight: bold">return</span> <span style="color: #008000; font-weight: bold">static_cast</span><span style="color: #666666">&lt;</span>Natural<span style="color: #666666">&gt;</span>(sqrt(<span style="color: #008000; font-weight: bold">static_cast</span><span style="color: #666666">&lt;</span><span style="color: #B00040">double</span><span style="color: #666666">&gt;</span>(x))); }
</div><div id="lc67">
</div><div id="lc68"><span style="color: #008000; font-weight: bold">template</span> <span style="color: #666666">&lt;</span><span style="color: #008000; font-weight: bold">typename</span> Natural<span style="color: #666666">&gt;</span>
</div><div id="lc69">generator(primes, Natural, primes<span style="color: #666666">&lt;</span>Natural<span style="color: #666666">&gt;</span>)
</div><div id="lc70">{
</div><div id="lc71"><span style="color: #008000; font-weight: bold">public</span><span style="color: #666666">:</span>
</div><div id="lc72">    <span style="color: #008000; font-weight: bold">typedef</span> Natural nat_type;
</div><div id="lc73">
</div><div id="lc74">    primes(nat_type n <span style="color: #666666">=</span> <span style="color: #666666">2</span>)
</div><div id="lc75">        <span style="color: #666666">:</span> n_(n)
</div><div id="lc76">        , sq_n_(sqrt_int(n))
</div><div id="lc77">    { }
</div><div id="lc78">
</div><div id="lc79">    emit(nat_type)
</div><div id="lc80">    {
</div><div id="lc81">        <span style="color: #008000; font-weight: bold">if</span> (n_ <span style="color: #666666">&lt;=</span> <span style="color: #666666">2</span>) yield(<span style="color: #666666">2</span>);
</div><div id="lc82">        <span style="color: #008000; font-weight: bold">if</span> (n_ <span style="color: #666666">&lt;=</span> <span style="color: #666666">3</span>) yield(<span style="color: #666666">3</span>);
</div><div id="lc83">        <span style="color: #008000; font-weight: bold">if</span> (n_ <span style="color: #666666">&lt;=</span> <span style="color: #666666">5</span>) yield(<span style="color: #666666">5</span>);
</div><div id="lc84">        <span style="color: #008000; font-weight: bold">if</span> (n_ <span style="color: #666666">&lt;=</span> <span style="color: #666666">7</span>) yield(<span style="color: #666666">7</span>);
</div><div id="lc85">        ps_.reset(<span style="color: #008000; font-weight: bold">new</span> primes(<span style="color: #666666">3</span>));
</div><div id="lc86">        ps_<span style="color: #666666">-&gt;</span>next();
</div><div id="lc87">        p1_ <span style="color: #666666">=</span> ps_<span style="color: #666666">-&gt;</span>value();
</div><div id="lc88">        <span style="color: #008000; font-weight: bold">for</span> (;;)
</div><div id="lc89">        {
</div><div id="lc90">            p0_ <span style="color: #666666">=</span> p1_;
</div><div id="lc91">            ps_<span style="color: #666666">-&gt;</span>next();
</div><div id="lc92">            p1_ <span style="color: #666666">=</span> ps_<span style="color: #666666">-&gt;</span>value();
</div><div id="lc93">            <span style="color: #008000; font-weight: bold">if</span> (p1_ <span style="color: #666666">&lt;=</span> sq_n_)
</div><div id="lc94">                <span style="color: #008000; font-weight: bold">continue</span>;
</div><div id="lc95">            gmap_.reset(<span style="color: #008000; font-weight: bold">new</span> gen_map<span style="color: #666666">&lt;</span>primes<span style="color: #666666">&gt;</span>(p0_, p1_));
</div><div id="lc96">            <span style="color: #008000; font-weight: bold">for</span> (; gmap_<span style="color: #666666">-&gt;</span>avail(); gmap_<span style="color: #666666">-&gt;</span>next())
</div><div id="lc97">                <span style="color: #008000; font-weight: bold">if</span> (gmap_<span style="color: #666666">-&gt;</span>value() <span style="color: #666666">&gt;=</span> n_)
</div><div id="lc98">                    yield(gmap_<span style="color: #666666">-&gt;</span>value());
</div><div id="lc99">        }
</div><div id="lc100">    }
</div><div id="lc101">    stop_emit()
</div><div id="lc102">
</div><div id="lc103"><span style="color: #008000; font-weight: bold">private</span><span style="color: #666666">:</span>
</div><div id="lc104">    <span style="color: #008000; font-weight: bold">const</span> nat_type n_, sq_n_;
</div><div id="lc105">    std<span style="color: #666666">::</span>auto_ptr<span style="color: #666666">&lt;</span>gen_map<span style="color: #666666">&lt;</span>primes<span style="color: #666666">&gt;</span> <span style="color: #666666">&gt;</span> gmap_;
</div><div id="lc106">    nat_type p0_, p1_;
</div><div id="lc107">    std<span style="color: #666666">::</span>auto_ptr<span style="color: #666666">&lt;</span>primes<span style="color: #666666">&gt;</span> ps_;
</div><div id="lc108">};
</div><div id="lc109">
</div><div id="lc110"><span style="color: #B00040">int</span> main()
</div><div id="lc111">{
</div><div id="lc112">    primes<span style="color: #666666">&lt;</span>word_t<span style="color: #666666">&gt;</span> ps(<span style="color: #666666">100000000</span>);
</div><div id="lc113">    word_t sum <span style="color: #666666">=</span> <span style="color: #666666">0</span>;
</div><div id="lc114">    <span style="color: #B00040">long</span> tim0 <span style="color: #666666">=</span> clock();
</div><div id="lc115">    <span style="color: #008000; font-weight: bold">for</span> (ps.next(); ps.value() <span style="color: #666666">&lt;=</span> <span style="color: #666666">120000000</span>; ps.next(), <span style="color: #666666">++</span>sum);
</div><div id="lc116">    printf(<span style="color: #BA2121">&quot;sum = %u, time: %0.3f sec.</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">&quot;</span>, sum, (clock() <span style="color: #666666">-</span> tim0) <span style="color: #666666">/</span> <span style="color: #666666">1000.0</span>);
</div><div id="lc117">}
</div></pre></div>
<p style="padding: 0; margin: 2em 0 1em 0; font-size: 0.8em; color: #666;"><span style="padding: 0 1em; background-color: #f5f5f5;"> Colored with <a style="color: #333" href="http://dumpz.org">dumpz.org</a></span></p>

BBCODE Copy To Clipboarddone!

[color=#BC7A00]#include <memory>
#include <math.h>
#include <time.h>
#include "../generator.h"
[/color]
[color=#008000][b]typedef[/b][/color] [color=#B00040]unsigned[/color] word_t;
[color=#008000][b]const[/b][/color] word_t bits_in_word [color=#666666]=[/color] [color=#666666]8[/color] [color=#666666]*[/color] [color=#008000][b]sizeof[/b][/color](word_t);

[color=#008000][b]template[/b][/color] [color=#666666]<[/color][color=#008000][b]typename[/b][/color] Primes[color=#666666]>[/color]
[color=#008000][b]struct[/b][/color] gen_map
{
    [color=#008000][b]typedef[/b][/color] [color=#008000][b]typename[/b][/color] Primes[color=#666666]::[/color]nat_type nat_type;

gen_map(nat_type p0, nat_type p1)
        [color=#666666]:[/color] lo_(p0 [color=#666666]*[/color] p0)
        , hi_(p1 [color=#666666]*[/color] p1)
        , bound_((hi_ [color=#666666]-[/color] lo_) [color=#666666]/[/color] [color=#666666]2[/color] [color=#666666]-[/color] [color=#666666]1[/color])
        , arr_([color=#008000][b]new[/b][/color] word_t [bound_ [color=#666666]/[/color] bits_in_word [color=#666666]+[/color] [color=#666666]1[/color]])
        , i_([color=#666666]~[/color]nat_type([color=#666666]0[/color]))
        , n_(lo_)
    {
        [color=#008000][b]for[/b][/color] (word_t i [color=#666666]=[/color] [color=#666666]0[/color]
            ; i [color=#666666]!=[/color] bound_ [color=#666666]/[/color] bits_in_word [color=#666666]+[/color] [color=#666666]1[/color]
            ; [color=#666666]++[/color]i)
            arr_[i] [color=#666666]=[/color] word_t([color=#666666]0[/color]);
        Primes ps([color=#666666]3[/color]);
        [color=#008000][b]for[/b][/color] (ps.next(); ps.value() [color=#666666]!=[/color] p1; ps.next())
        {
            [color=#008000][b]const[/b][/color] nat_type i [color=#666666]=[/color] ps.value();
            [color=#008000][b]for[/b][/color] (nat_type j [color=#666666]=[/color] correct(i [color=#666666]-[/color] lo_ [color=#666666]%[/color] i, i) [color=#666666]/[/color] [color=#666666]2[/color] [color=#666666]-[/color] [color=#666666]1[/color]
                ; j [color=#666666]<[/color] bound_
                ; j [color=#666666]+=[/color] i)
                arr_[j [color=#666666]/[/color] bits_in_word] [color=#666666]|=[/color] [color=#666666]1[/color] [color=#666666]<<[/color] (j [color=#666666]%[/color] bits_in_word);
        }
        next();
    }

[color=#666666]~[/color]gen_map()
    { [color=#008000][b]delete[/b][/color][] arr_; }

[color=#B00040]bool[/color] avail() [color=#008000][b]const[/b][/color]
    { [color=#008000][b]return[/b][/color] i_ [color=#666666]!=[/color] bound_; }

nat_type value() [color=#008000][b]const[/b][/color]
    { [color=#008000][b]return[/b][/color] n_; }

[color=#B00040]void[/color] next()
    {
        [color=#008000][b]do[/b][/color] { [color=#666666]++[/color]i_; n_ [color=#666666]+=[/color] [color=#666666]2[/color]; }
        [color=#008000][b]while[/b][/color] (
            avail() [color=#666666]&&[/color]
            (arr_[i_ [color=#666666]/[/color] bits_in_word] [color=#666666]&[/color] ([color=#666666]1[/color] [color=#666666]<<[/color] (i_ [color=#666666]%[/color] bits_in_word))));
    }

[color=#008000][b]private[/b][/color][color=#666666]:[/color]
    [color=#008000][b]static[/b][/color] nat_type correct(nat_type n, nat_type i)
    { [color=#008000][b]return[/b][/color] n [color=#666666]&[/color] [color=#666666]1[/color] [color=#666666]?[/color] n [color=#666666]+[/color] i [color=#666666]:[/color] n; }

[color=#008000][b]const[/b][/color] nat_type lo_, hi_, bound_;
    word_t [color=#666666]*[/color]arr_;
    nat_type i_, n_;
};

[color=#008000][b]template[/b][/color] [color=#666666]<[/color][color=#008000][b]typename[/b][/color] Natural[color=#666666]>[/color]
[color=#008000][b]inline[/b][/color] Natural sqrt_int(Natural x)
{ [color=#008000][b]return[/b][/color] [color=#008000][b]static_cast[/b][/color][color=#666666]<[/color]Natural[color=#666666]>[/color](sqrt([color=#008000][b]static_cast[/b][/color][color=#666666]<[/color][color=#B00040]double[/color][color=#666666]>[/color](x))); }

[color=#008000][b]template[/b][/color] [color=#666666]<[/color][color=#008000][b]typename[/b][/color] Natural[color=#666666]>[/color]
generator(primes, Natural, primes[color=#666666]<[/color]Natural[color=#666666]>[/color])
{
[color=#008000][b]public[/b][/color][color=#666666]:[/color]
    [color=#008000][b]typedef[/b][/color] Natural nat_type;

primes(nat_type n [color=#666666]=[/color] [color=#666666]2[/color])
        [color=#666666]:[/color] n_(n)
        , sq_n_(sqrt_int(n))
    { }

emit(nat_type)
    {
        [color=#008000][b]if[/b][/color] (n_ [color=#666666]<=[/color] [color=#666666]2[/color]) yield([color=#666666]2[/color]);
        [color=#008000][b]if[/b][/color] (n_ [color=#666666]<=[/color] [color=#666666]3[/color]) yield([color=#666666]3[/color]);
        [color=#008000][b]if[/b][/color] (n_ [color=#666666]<=[/color] [color=#666666]5[/color]) yield([color=#666666]5[/color]);
        [color=#008000][b]if[/b][/color] (n_ [color=#666666]<=[/color] [color=#666666]7[/color]) yield([color=#666666]7[/color]);
        ps_.reset([color=#008000][b]new[/b][/color] primes([color=#666666]3[/color]));
        ps_[color=#666666]->[/color]next();
        p1_ [color=#666666]=[/color] ps_[color=#666666]->[/color]value();
        [color=#008000][b]for[/b][/color] (;;)
        {
            p0_ [color=#666666]=[/color] p1_;
            ps_[color=#666666]->[/color]next();
            p1_ [color=#666666]=[/color] ps_[color=#666666]->[/color]value();
            [color=#008000][b]if[/b][/color] (p1_ [color=#666666]<=[/color] sq_n_)
                [color=#008000][b]continue[/b][/color];
            gmap_.reset([color=#008000][b]new[/b][/color] gen_map[color=#666666]<[/color]primes[color=#666666]>[/color](p0_, p1_));
            [color=#008000][b]for[/b][/color] (; gmap_[color=#666666]->[/color]avail(); gmap_[color=#666666]->[/color]next())
                [color=#008000][b]if[/b][/color] (gmap_[color=#666666]->[/color]value() [color=#666666]>=[/color] n_)
                    yield(gmap_[color=#666666]->[/color]value());
        }
    }
    stop_emit()

[color=#008000][b]private[/b][/color][color=#666666]:[/color]
    [color=#008000][b]const[/b][/color] nat_type n_, sq_n_;
    std[color=#666666]::[/color]auto_ptr[color=#666666]<[/color]gen_map[color=#666666]<[/color]primes[color=#666666]>[/color] [color=#666666]>[/color] gmap_;
    nat_type p0_, p1_;
    std[color=#666666]::[/color]auto_ptr[color=#666666]<[/color]primes[color=#666666]>[/color] ps_;
};

[color=#B00040]int[/color] main()
{
    primes[color=#666666]<[/color]word_t[color=#666666]>[/color] ps([color=#666666]100000000[/color]);
    word_t sum [color=#666666]=[/color] [color=#666666]0[/color];
    [color=#B00040]long[/color] tim0 [color=#666666]=[/color] clock();
    [color=#008000][b]for[/b][/color] (ps.next(); ps.value() [color=#666666]<=[/color] [color=#666666]120000000[/color]; ps.next(), [color=#666666]++[/color]sum);
    printf([color=#BA2121]"sum = %u, time: %0.3f sec.[/color][color=#BB6622][b]\n[/b][/color][color=#BA2121]"[/color], sum, (clock() [color=#666666]-[/color] tim0) [color=#666666]/[/color] [color=#666666]1000.0[/color]);
}

--------------------------------------
Colored with http://dumpz.org

Light HTML Copy To Clipboarddone!

That method generates HTML with CSS classes. Hence you'll need the style sheet file

<div class="highlight"><pre><div id="lc1"><span class="cp">#include &lt;memory&gt;</span>
</div><div id="lc2"><span class="cp">#include &lt;math.h&gt;</span>
</div><div id="lc3"><span class="cp">#include &lt;time.h&gt;</span>
</div><div id="lc4"><span class="cp">#include &quot;../generator.h&quot;</span>
</div><div id="lc5">
</div><div id="lc6"><span class="k">typedef</span> <span class="kt">unsigned</span> <span class="n">word_t</span><span class="p">;</span>
</div><div id="lc7"><span class="k">const</span> <span class="n">word_t</span> <span class="n">bits_in_word</span> <span class="o">=</span> <span class="mi">8</span> <span class="o">*</span> <span class="k">sizeof</span><span class="p">(</span><span class="n">word_t</span><span class="p">);</span>
</div><div id="lc8">
</div><div id="lc9"><span class="k">template</span> <span class="o">&lt;</span><span class="k">typename</span> <span class="n">Primes</span><span class="o">&gt;</span>
</div><div id="lc10"><span class="k">struct</span> <span class="n">gen_map</span>
</div><div id="lc11"><span class="p">{</span>
</div><div id="lc12">    <span class="k">typedef</span> <span class="k">typename</span> <span class="n">Primes</span><span class="o">::</span><span class="n">nat_type</span> <span class="n">nat_type</span><span class="p">;</span>
</div><div id="lc13">
</div><div id="lc14">    <span class="n">gen_map</span><span class="p">(</span><span class="n">nat_type</span> <span class="n">p0</span><span class="p">,</span> <span class="n">nat_type</span> <span class="n">p1</span><span class="p">)</span>
</div><div id="lc15">        <span class="o">:</span> <span class="n">lo_</span><span class="p">(</span><span class="n">p0</span> <span class="o">*</span> <span class="n">p0</span><span class="p">)</span>
</div><div id="lc16">        <span class="p">,</span> <span class="n">hi_</span><span class="p">(</span><span class="n">p1</span> <span class="o">*</span> <span class="n">p1</span><span class="p">)</span>
</div><div id="lc17">        <span class="p">,</span> <span class="n">bound_</span><span class="p">((</span><span class="n">hi_</span> <span class="o">-</span> <span class="n">lo_</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>
</div><div id="lc18">        <span class="p">,</span> <span class="n">arr_</span><span class="p">(</span><span class="k">new</span> <span class="n">word_t</span> <span class="p">[</span><span class="n">bound_</span> <span class="o">/</span> <span class="n">bits_in_word</span> <span class="o">+</span> <span class="mi">1</span><span class="p">])</span>
</div><div id="lc19">        <span class="p">,</span> <span class="n">i_</span><span class="p">(</span><span class="o">~</span><span class="n">nat_type</span><span class="p">(</span><span class="mi">0</span><span class="p">))</span>
</div><div id="lc20">        <span class="p">,</span> <span class="n">n_</span><span class="p">(</span><span class="n">lo_</span><span class="p">)</span>
</div><div id="lc21">    <span class="p">{</span>
</div><div id="lc22">        <span class="k">for</span> <span class="p">(</span><span class="n">word_t</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span>
</div><div id="lc23">            <span class="p">;</span> <span class="n">i</span> <span class="o">!=</span> <span class="n">bound_</span> <span class="o">/</span> <span class="n">bits_in_word</span> <span class="o">+</span> <span class="mi">1</span>
</div><div id="lc24">            <span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
</div><div id="lc25">            <span class="n">arr_</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">word_t</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
</div><div id="lc26">        <span class="n">Primes</span> <span class="n">ps</span><span class="p">(</span><span class="mi">3</span><span class="p">);</span>
</div><div id="lc27">        <span class="k">for</span> <span class="p">(</span><span class="n">ps</span><span class="p">.</span><span class="n">next</span><span class="p">();</span> <span class="n">ps</span><span class="p">.</span><span class="n">value</span><span class="p">()</span> <span class="o">!=</span> <span class="n">p1</span><span class="p">;</span> <span class="n">ps</span><span class="p">.</span><span class="n">next</span><span class="p">())</span>
</div><div id="lc28">        <span class="p">{</span>
</div><div id="lc29">            <span class="k">const</span> <span class="n">nat_type</span> <span class="n">i</span> <span class="o">=</span> <span class="n">ps</span><span class="p">.</span><span class="n">value</span><span class="p">();</span>
</div><div id="lc30">            <span class="k">for</span> <span class="p">(</span><span class="n">nat_type</span> <span class="n">j</span> <span class="o">=</span> <span class="n">correct</span><span class="p">(</span><span class="n">i</span> <span class="o">-</span> <span class="n">lo_</span> <span class="o">%</span> <span class="n">i</span><span class="p">,</span> <span class="n">i</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span> <span class="o">-</span> <span class="mi">1</span>
</div><div id="lc31">                <span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">bound_</span>
</div><div id="lc32">                <span class="p">;</span> <span class="n">j</span> <span class="o">+=</span> <span class="n">i</span><span class="p">)</span>
</div><div id="lc33">                <span class="n">arr_</span><span class="p">[</span><span class="n">j</span> <span class="o">/</span> <span class="n">bits_in_word</span><span class="p">]</span> <span class="o">|=</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="p">(</span><span class="n">j</span> <span class="o">%</span> <span class="n">bits_in_word</span><span class="p">);</span>
</div><div id="lc34">        <span class="p">}</span>
</div><div id="lc35">        <span class="n">next</span><span class="p">();</span>
</div><div id="lc36">    <span class="p">}</span>
</div><div id="lc37">
</div><div id="lc38">    <span class="o">~</span><span class="n">gen_map</span><span class="p">()</span>
</div><div id="lc39">    <span class="p">{</span> <span class="k">delete</span><span class="p">[]</span> <span class="n">arr_</span><span class="p">;</span> <span class="p">}</span>
</div><div id="lc40">
</div><div id="lc41">    <span class="kt">bool</span> <span class="n">avail</span><span class="p">()</span> <span class="k">const</span>
</div><div id="lc42">    <span class="p">{</span> <span class="k">return</span> <span class="n">i_</span> <span class="o">!=</span> <span class="n">bound_</span><span class="p">;</span> <span class="p">}</span>
</div><div id="lc43">
</div><div id="lc44">    <span class="n">nat_type</span> <span class="n">value</span><span class="p">()</span> <span class="k">const</span>
</div><div id="lc45">    <span class="p">{</span> <span class="k">return</span> <span class="n">n_</span><span class="p">;</span> <span class="p">}</span>
</div><div id="lc46">
</div><div id="lc47">    <span class="kt">void</span> <span class="n">next</span><span class="p">()</span>
</div><div id="lc48">    <span class="p">{</span>
</div><div id="lc49">        <span class="k">do</span> <span class="p">{</span> <span class="o">++</span><span class="n">i_</span><span class="p">;</span> <span class="n">n_</span> <span class="o">+=</span> <span class="mi">2</span><span class="p">;</span> <span class="p">}</span>
</div><div id="lc50">        <span class="k">while</span> <span class="p">(</span>
</div><div id="lc51">            <span class="n">avail</span><span class="p">()</span> <span class="o">&amp;&amp;</span>
</div><div id="lc52">            <span class="p">(</span><span class="n">arr_</span><span class="p">[</span><span class="n">i_</span> <span class="o">/</span> <span class="n">bits_in_word</span><span class="p">]</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="p">(</span><span class="n">i_</span> <span class="o">%</span> <span class="n">bits_in_word</span><span class="p">))));</span>
</div><div id="lc53">    <span class="p">}</span>
</div><div id="lc54">
</div><div id="lc55"><span class="k">private</span><span class="o">:</span>
</div><div id="lc56">    <span class="k">static</span> <span class="n">nat_type</span> <span class="n">correct</span><span class="p">(</span><span class="n">nat_type</span> <span class="n">n</span><span class="p">,</span> <span class="n">nat_type</span> <span class="n">i</span><span class="p">)</span>
</div><div id="lc57">    <span class="p">{</span> <span class="k">return</span> <span class="n">n</span> <span class="o">&amp;</span> <span class="mi">1</span> <span class="o">?</span> <span class="n">n</span> <span class="o">+</span> <span class="n">i</span> <span class="o">:</span> <span class="n">n</span><span class="p">;</span> <span class="p">}</span>
</div><div id="lc58">
</div><div id="lc59">    <span class="k">const</span> <span class="n">nat_type</span> <span class="n">lo_</span><span class="p">,</span> <span class="n">hi_</span><span class="p">,</span> <span class="n">bound_</span><span class="p">;</span>
</div><div id="lc60">    <span class="n">word_t</span> <span class="o">*</span><span class="n">arr_</span><span class="p">;</span>
</div><div id="lc61">    <span class="n">nat_type</span> <span class="n">i_</span><span class="p">,</span> <span class="n">n_</span><span class="p">;</span>
</div><div id="lc62"><span class="p">};</span>
</div><div id="lc63">
</div><div id="lc64"><span class="k">template</span> <span class="o">&lt;</span><span class="k">typename</span> <span class="n">Natural</span><span class="o">&gt;</span>
</div><div id="lc65"><span class="kr">inline</span> <span class="n">Natural</span> <span class="n">sqrt_int</span><span class="p">(</span><span class="n">Natural</span> <span class="n">x</span><span class="p">)</span>
</div><div id="lc66"><span class="p">{</span> <span class="k">return</span> <span class="k">static_cast</span><span class="o">&lt;</span><span class="n">Natural</span><span class="o">&gt;</span><span class="p">(</span><span class="n">sqrt</span><span class="p">(</span><span class="k">static_cast</span><span class="o">&lt;</span><span class="kt">double</span><span class="o">&gt;</span><span class="p">(</span><span class="n">x</span><span class="p">)));</span> <span class="p">}</span>
</div><div id="lc67">
</div><div id="lc68"><span class="k">template</span> <span class="o">&lt;</span><span class="k">typename</span> <span class="n">Natural</span><span class="o">&gt;</span>
</div><div id="lc69"><span class="n">generator</span><span class="p">(</span><span class="n">primes</span><span class="p">,</span> <span class="n">Natural</span><span class="p">,</span> <span class="n">primes</span><span class="o">&lt;</span><span class="n">Natural</span><span class="o">&gt;</span><span class="p">)</span>
</div><div id="lc70"><span class="p">{</span>
</div><div id="lc71"><span class="k">public</span><span class="o">:</span>
</div><div id="lc72">    <span class="k">typedef</span> <span class="n">Natural</span> <span class="n">nat_type</span><span class="p">;</span>
</div><div id="lc73">
</div><div id="lc74">    <span class="n">primes</span><span class="p">(</span><span class="n">nat_type</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">2</span><span class="p">)</span>
</div><div id="lc75">        <span class="o">:</span> <span class="n">n_</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
</div><div id="lc76">        <span class="p">,</span> <span class="n">sq_n_</span><span class="p">(</span><span class="n">sqrt_int</span><span class="p">(</span><span class="n">n</span><span class="p">))</span>
</div><div id="lc77">    <span class="p">{</span> <span class="p">}</span>
</div><div id="lc78">
</div><div id="lc79">    <span class="n">emit</span><span class="p">(</span><span class="n">nat_type</span><span class="p">)</span>
</div><div id="lc80">    <span class="p">{</span>
</div><div id="lc81">        <span class="k">if</span> <span class="p">(</span><span class="n">n_</span> <span class="o">&lt;=</span> <span class="mi">2</span><span class="p">)</span> <span class="n">yield</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span>
</div><div id="lc82">        <span class="k">if</span> <span class="p">(</span><span class="n">n_</span> <span class="o">&lt;=</span> <span class="mi">3</span><span class="p">)</span> <span class="n">yield</span><span class="p">(</span><span class="mi">3</span><span class="p">);</span>
</div><div id="lc83">        <span class="k">if</span> <span class="p">(</span><span class="n">n_</span> <span class="o">&lt;=</span> <span class="mi">5</span><span class="p">)</span> <span class="n">yield</span><span class="p">(</span><span class="mi">5</span><span class="p">);</span>
</div><div id="lc84">        <span class="k">if</span> <span class="p">(</span><span class="n">n_</span> <span class="o">&lt;=</span> <span class="mi">7</span><span class="p">)</span> <span class="n">yield</span><span class="p">(</span><span class="mi">7</span><span class="p">);</span>
</div><div id="lc85">        <span class="n">ps_</span><span class="p">.</span><span class="n">reset</span><span class="p">(</span><span class="k">new</span> <span class="n">primes</span><span class="p">(</span><span class="mi">3</span><span class="p">));</span>
</div><div id="lc86">        <span class="n">ps_</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">();</span>
</div><div id="lc87">        <span class="n">p1_</span> <span class="o">=</span> <span class="n">ps_</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">();</span>
</div><div id="lc88">        <span class="k">for</span> <span class="p">(;;)</span>
</div><div id="lc89">        <span class="p">{</span>
</div><div id="lc90">            <span class="n">p0_</span> <span class="o">=</span> <span class="n">p1_</span><span class="p">;</span>
</div><div id="lc91">            <span class="n">ps_</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">();</span>
</div><div id="lc92">            <span class="n">p1_</span> <span class="o">=</span> <span class="n">ps_</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">();</span>
</div><div id="lc93">            <span class="k">if</span> <span class="p">(</span><span class="n">p1_</span> <span class="o">&lt;=</span> <span class="n">sq_n_</span><span class="p">)</span>
</div><div id="lc94">                <span class="k">continue</span><span class="p">;</span>
</div><div id="lc95">            <span class="n">gmap_</span><span class="p">.</span><span class="n">reset</span><span class="p">(</span><span class="k">new</span> <span class="n">gen_map</span><span class="o">&lt;</span><span class="n">primes</span><span class="o">&gt;</span><span class="p">(</span><span class="n">p0_</span><span class="p">,</span> <span class="n">p1_</span><span class="p">));</span>
</div><div id="lc96">            <span class="k">for</span> <span class="p">(;</span> <span class="n">gmap_</span><span class="o">-&gt;</span><span class="n">avail</span><span class="p">();</span> <span class="n">gmap_</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">())</span>
</div><div id="lc97">                <span class="k">if</span> <span class="p">(</span><span class="n">gmap_</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">()</span> <span class="o">&gt;=</span> <span class="n">n_</span><span class="p">)</span>
</div><div id="lc98">                    <span class="n">yield</span><span class="p">(</span><span class="n">gmap_</span><span class="o">-&gt;</span><span class="n">value</span><span class="p">());</span>
</div><div id="lc99">        <span class="p">}</span>
</div><div id="lc100">    <span class="p">}</span>
</div><div id="lc101">    <span class="n">stop_emit</span><span class="p">()</span>
</div><div id="lc102">
</div><div id="lc103"><span class="k">private</span><span class="o">:</span>
</div><div id="lc104">    <span class="k">const</span> <span class="n">nat_type</span> <span class="n">n_</span><span class="p">,</span> <span class="n">sq_n_</span><span class="p">;</span>
</div><div id="lc105">    <span class="n">std</span><span class="o">::</span><span class="n">auto_ptr</span><span class="o">&lt;</span><span class="n">gen_map</span><span class="o">&lt;</span><span class="n">primes</span><span class="o">&gt;</span> <span class="o">&gt;</span> <span class="n">gmap_</span><span class="p">;</span>
</div><div id="lc106">    <span class="n">nat_type</span> <span class="n">p0_</span><span class="p">,</span> <span class="n">p1_</span><span class="p">;</span>
</div><div id="lc107">    <span class="n">std</span><span class="o">::</span><span class="n">auto_ptr</span><span class="o">&lt;</span><span class="n">primes</span><span class="o">&gt;</span> <span class="n">ps_</span><span class="p">;</span>
</div><div id="lc108"><span class="p">};</span>
</div><div id="lc109">
</div><div id="lc110"><span class="kt">int</span> <span class="n">main</span><span class="p">()</span>
</div><div id="lc111"><span class="p">{</span>
</div><div id="lc112">    <span class="n">primes</span><span class="o">&lt;</span><span class="n">word_t</span><span class="o">&gt;</span> <span class="n">ps</span><span class="p">(</span><span class="mi">100000000</span><span class="p">);</span>
</div><div id="lc113">    <span class="n">word_t</span> <span class="n">sum</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
</div><div id="lc114">    <span class="kt">long</span> <span class="n">tim0</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
</div><div id="lc115">    <span class="k">for</span> <span class="p">(</span><span class="n">ps</span><span class="p">.</span><span class="n">next</span><span class="p">();</span> <span class="n">ps</span><span class="p">.</span><span class="n">value</span><span class="p">()</span> <span class="o">&lt;=</span> <span class="mi">120000000</span><span class="p">;</span> <span class="n">ps</span><span class="p">.</span><span class="n">next</span><span class="p">(),</span> <span class="o">++</span><span class="n">sum</span><span class="p">);</span>
</div><div id="lc116">    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;sum = %u, time: %0.3f sec.</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">sum</span><span class="p">,</span> <span class="p">(</span><span class="n">clock</span><span class="p">()</span> <span class="o">-</span> <span class="n">tim0</span><span class="p">)</span> <span class="o">/</span> <span class="mf">1000.0</span><span class="p">);</span>
</div><div id="lc117"><span class="p">}</span>
</div></pre></div>
<p style="padding: 0; margin: 2em 0 1em 0; font-size: 0.8em; color: #666;"><span style="padding: 0 1em; background-color: #f5f5f5;"> Colored with <a style="color: #333" href="http://dumpz.org">dumpz.org</a></span></p>

Habrahabr.ru HTML Copy To Clipboarddone!

Use that HTML for publications on habrahabr.ru

<blockquote><code><font color="#BC7A00">#include&nbsp;&lt;memory&gt;
#include&nbsp;&lt;math.h&gt;
#include&nbsp;&lt;time.h&gt;
#include&nbsp;&quot;../generator.h&quot;
</font>
<font color="#008000"><strong>typedef</strong></font>&nbsp;<font color="#B00040">unsigned</font>&nbsp;word_t;
<font color="#008000"><strong>const</strong></font>&nbsp;word_t&nbsp;bits_in_word&nbsp;<font color="#666666">=</font>&nbsp;<font color="#666666">8</font>&nbsp;<font color="#666666">*</font>&nbsp;<font color="#008000"><strong>sizeof</strong></font>(word_t);

<font color="#008000"><strong>template</strong></font>&nbsp;<font color="#666666">&lt;</font><font color="#008000"><strong>typename</strong></font>&nbsp;Primes<font color="#666666">&gt;</font>
<font color="#008000"><strong>struct</strong></font>&nbsp;gen_map
{
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>typedef</strong></font>&nbsp;<font color="#008000"><strong>typename</strong></font>&nbsp;Primes<font color="#666666">::</font>nat_type&nbsp;nat_type;

&nbsp;&nbsp;&nbsp;&nbsp;gen_map(nat_type&nbsp;p0,&nbsp;nat_type&nbsp;p1)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">:</font>&nbsp;lo_(p0&nbsp;<font color="#666666">*</font>&nbsp;p0)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;hi_(p1&nbsp;<font color="#666666">*</font>&nbsp;p1)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;bound_((hi_&nbsp;<font color="#666666">-</font>&nbsp;lo_)&nbsp;<font color="#666666">/</font>&nbsp;<font color="#666666">2</font>&nbsp;<font color="#666666">-</font>&nbsp;<font color="#666666">1</font>)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;arr_(<font color="#008000"><strong>new</strong></font>&nbsp;word_t&nbsp;[bound_&nbsp;<font color="#666666">/</font>&nbsp;bits_in_word&nbsp;<font color="#666666">+</font>&nbsp;<font color="#666666">1</font>])
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;i_(<font color="#666666">~</font>nat_type(<font color="#666666">0</font>))
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;n_(lo_)
&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>&nbsp;(word_t&nbsp;i&nbsp;<font color="#666666">=</font>&nbsp;<font color="#666666">0</font>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;&nbsp;i&nbsp;<font color="#666666">!=</font>&nbsp;bound_&nbsp;<font color="#666666">/</font>&nbsp;bits_in_word&nbsp;<font color="#666666">+</font>&nbsp;<font color="#666666">1</font>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;&nbsp;<font color="#666666">++</font>i)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr_[i]&nbsp;<font color="#666666">=</font>&nbsp;word_t(<font color="#666666">0</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Primes&nbsp;ps(<font color="#666666">3</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>&nbsp;(ps.next();&nbsp;ps.value()&nbsp;<font color="#666666">!=</font>&nbsp;p1;&nbsp;ps.next())
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>const</strong></font>&nbsp;nat_type&nbsp;i&nbsp;<font color="#666666">=</font>&nbsp;ps.value();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>&nbsp;(nat_type&nbsp;j&nbsp;<font color="#666666">=</font>&nbsp;correct(i&nbsp;<font color="#666666">-</font>&nbsp;lo_&nbsp;<font color="#666666">%</font>&nbsp;i,&nbsp;i)&nbsp;<font color="#666666">/</font>&nbsp;<font color="#666666">2</font>&nbsp;<font color="#666666">-</font>&nbsp;<font color="#666666">1</font>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;&nbsp;j&nbsp;<font color="#666666">&lt;</font>&nbsp;bound_
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;;&nbsp;j&nbsp;<font color="#666666">+=</font>&nbsp;i)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr_[j&nbsp;<font color="#666666">/</font>&nbsp;bits_in_word]&nbsp;<font color="#666666">|=</font>&nbsp;<font color="#666666">1</font>&nbsp;<font color="#666666">&lt;&lt;</font>&nbsp;(j&nbsp;<font color="#666666">%</font>&nbsp;bits_in_word);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next();
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">~</font>gen_map()
&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;<font color="#008000"><strong>delete</strong></font>[]&nbsp;arr_;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">bool</font>&nbsp;avail()&nbsp;<font color="#008000"><strong>const</strong></font>
&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;i_&nbsp;<font color="#666666">!=</font>&nbsp;bound_;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;nat_type&nbsp;value()&nbsp;<font color="#008000"><strong>const</strong></font>
&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;n_;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">void</font>&nbsp;next()
&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>do</strong></font>&nbsp;{&nbsp;<font color="#666666">++</font>i_;&nbsp;n_&nbsp;<font color="#666666">+=</font>&nbsp;<font color="#666666">2</font>;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>while</strong></font>&nbsp;(
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;avail()&nbsp;<font color="#666666">&amp;&amp;</font>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(arr_[i_&nbsp;<font color="#666666">/</font>&nbsp;bits_in_word]&nbsp;<font color="#666666">&amp;</font>&nbsp;(<font color="#666666">1</font>&nbsp;<font color="#666666">&lt;&lt;</font>&nbsp;(i_&nbsp;<font color="#666666">%</font>&nbsp;bits_in_word))));
&nbsp;&nbsp;&nbsp;&nbsp;}

<font color="#008000"><strong>private</strong></font><font color="#666666">:</font>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>static</strong></font>&nbsp;nat_type&nbsp;correct(nat_type&nbsp;n,&nbsp;nat_type&nbsp;i)
&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;n&nbsp;<font color="#666666">&amp;</font>&nbsp;<font color="#666666">1</font>&nbsp;<font color="#666666">?</font>&nbsp;n&nbsp;<font color="#666666">+</font>&nbsp;i&nbsp;<font color="#666666">:</font>&nbsp;n;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>const</strong></font>&nbsp;nat_type&nbsp;lo_,&nbsp;hi_,&nbsp;bound_;
&nbsp;&nbsp;&nbsp;&nbsp;word_t&nbsp;<font color="#666666">*</font>arr_;
&nbsp;&nbsp;&nbsp;&nbsp;nat_type&nbsp;i_,&nbsp;n_;
};

<font color="#008000"><strong>template</strong></font>&nbsp;<font color="#666666">&lt;</font><font color="#008000"><strong>typename</strong></font>&nbsp;Natural<font color="#666666">&gt;</font>
<font color="#008000"><strong>inline</strong></font>&nbsp;Natural&nbsp;sqrt_int(Natural&nbsp;x)
{&nbsp;<font color="#008000"><strong>return</strong></font>&nbsp;<font color="#008000"><strong>static_cast</strong></font><font color="#666666">&lt;</font>Natural<font color="#666666">&gt;</font>(sqrt(<font color="#008000"><strong>static_cast</strong></font><font color="#666666">&lt;</font><font color="#B00040">double</font><font color="#666666">&gt;</font>(x)));&nbsp;}

<font color="#008000"><strong>template</strong></font>&nbsp;<font color="#666666">&lt;</font><font color="#008000"><strong>typename</strong></font>&nbsp;Natural<font color="#666666">&gt;</font>
generator(primes,&nbsp;Natural,&nbsp;primes<font color="#666666">&lt;</font>Natural<font color="#666666">&gt;</font>)
{
<font color="#008000"><strong>public</strong></font><font color="#666666">:</font>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>typedef</strong></font>&nbsp;Natural&nbsp;nat_type;

&nbsp;&nbsp;&nbsp;&nbsp;primes(nat_type&nbsp;n&nbsp;<font color="#666666">=</font>&nbsp;<font color="#666666">2</font>)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#666666">:</font>&nbsp;n_(n)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;sq_n_(sqrt_int(n))
&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;emit(nat_type)
&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>&nbsp;(n_&nbsp;<font color="#666666">&lt;=</font>&nbsp;<font color="#666666">2</font>)&nbsp;yield(<font color="#666666">2</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>&nbsp;(n_&nbsp;<font color="#666666">&lt;=</font>&nbsp;<font color="#666666">3</font>)&nbsp;yield(<font color="#666666">3</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>&nbsp;(n_&nbsp;<font color="#666666">&lt;=</font>&nbsp;<font color="#666666">5</font>)&nbsp;yield(<font color="#666666">5</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>&nbsp;(n_&nbsp;<font color="#666666">&lt;=</font>&nbsp;<font color="#666666">7</font>)&nbsp;yield(<font color="#666666">7</font>);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ps_.reset(<font color="#008000"><strong>new</strong></font>&nbsp;primes(<font color="#666666">3</font>));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ps_<font color="#666666">-&gt;</font>next();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p1_&nbsp;<font color="#666666">=</font>&nbsp;ps_<font color="#666666">-&gt;</font>value();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>&nbsp;(;;)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p0_&nbsp;<font color="#666666">=</font>&nbsp;p1_;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ps_<font color="#666666">-&gt;</font>next();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p1_&nbsp;<font color="#666666">=</font>&nbsp;ps_<font color="#666666">-&gt;</font>value();
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>&nbsp;(p1_&nbsp;<font color="#666666">&lt;=</font>&nbsp;sq_n_)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>continue</strong></font>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;gmap_.reset(<font color="#008000"><strong>new</strong></font>&nbsp;gen_map<font color="#666666">&lt;</font>primes<font color="#666666">&gt;</font>(p0_,&nbsp;p1_));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>&nbsp;(;&nbsp;gmap_<font color="#666666">-&gt;</font>avail();&nbsp;gmap_<font color="#666666">-&gt;</font>next())
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>if</strong></font>&nbsp;(gmap_<font color="#666666">-&gt;</font>value()&nbsp;<font color="#666666">&gt;=</font>&nbsp;n_)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield(gmap_<font color="#666666">-&gt;</font>value());
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;stop_emit()

<font color="#008000"><strong>private</strong></font><font color="#666666">:</font>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>const</strong></font>&nbsp;nat_type&nbsp;n_,&nbsp;sq_n_;
&nbsp;&nbsp;&nbsp;&nbsp;std<font color="#666666">::</font>auto_ptr<font color="#666666">&lt;</font>gen_map<font color="#666666">&lt;</font>primes<font color="#666666">&gt;</font>&nbsp;<font color="#666666">&gt;</font>&nbsp;gmap_;
&nbsp;&nbsp;&nbsp;&nbsp;nat_type&nbsp;p0_,&nbsp;p1_;
&nbsp;&nbsp;&nbsp;&nbsp;std<font color="#666666">::</font>auto_ptr<font color="#666666">&lt;</font>primes<font color="#666666">&gt;</font>&nbsp;ps_;
};

<font color="#B00040">int</font>&nbsp;main()
{
&nbsp;&nbsp;&nbsp;&nbsp;primes<font color="#666666">&lt;</font>word_t<font color="#666666">&gt;</font>&nbsp;ps(<font color="#666666">100000000</font>);
&nbsp;&nbsp;&nbsp;&nbsp;word_t&nbsp;sum&nbsp;<font color="#666666">=</font>&nbsp;<font color="#666666">0</font>;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#B00040">long</font>&nbsp;tim0&nbsp;<font color="#666666">=</font>&nbsp;clock();
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#008000"><strong>for</strong></font>&nbsp;(ps.next();&nbsp;ps.value()&nbsp;<font color="#666666">&lt;=</font>&nbsp;<font color="#666666">120000000</font>;&nbsp;ps.next(),&nbsp;<font color="#666666">++</font>sum);
&nbsp;&nbsp;&nbsp;&nbsp;printf(<font color="#BA2121">&quot;sum&nbsp;=&nbsp;%u,&nbsp;time:&nbsp;%0.3f&nbsp;sec.</font><font color="#BB6622"><strong>\n</strong></font><font color="#BA2121">&quot;</font>,&nbsp;sum,&nbsp;(clock()&nbsp;<font color="#666666">-</font>&nbsp;tim0)&nbsp;<font color="#666666">/</font>&nbsp;<font color="#666666">1000.0</font>);
}
</code></blockquote><p><font color="gray">Colored with <a href="http://dumpz.org">dumpz.org</a></p>