搜尋

首頁  >  文章  >  後端開發  >  如何编程最快速度求出两百万以内素数个数（不限语言和算法）？

如何编程最快速度求出两百万以内素数个数（不限语言和算法）？

WBOY
WBOY原創
2016-06-06 16:22:472240瀏覽

回复内容：

x贴一个优化得比较过分的线性筛。用位模式保存状态，直接绕过2和3的倍数。

<code class="language-c"><span class="cp">#include <stdio.h></stdio.h></span>
<span class="cp">#include <time.h></time.h></span>
<span class="cp">#include <string.h></string.h></span>
<span class="cp">#include <stdlib.h></stdlib.h></span>

<span class="cp">#define PRIME_LIM 10000000</span>
<span class="cp">#define N 100000000</span>

<span class="kt">int</span> <span class="n">primes</span><span class="p">[</span><span class="n">PRIME_LIM</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">};</span>
<span class="kt">int</span> <span class="n">flags</span><span class="p">[</span><span class="n">N</span><span class="o">/</span><span class="mi">96</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">};</span>

<span class="kt">int</span> <span class="nf">get_prime</span><span class="p">()</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">nu</span> <span class="o">=</span> <span class="mi">5</span><span class="p">,</span> <span class="n">to</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="n">primes</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span>
    <span class="n">primes</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mi">2</span><span class="p">,</span> <span class="n">primes</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="mi">3</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">nu</span> <span class="o"> <span class="n">N</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="p">(</span><span class="n">flags</span><span class="p">[</span><span class="n">i</span><span class="o">>></span><span class="mi">5</span><span class="p">]</span><span class="o">&</span><span class="p">(</span><span class="mi">1</span><span class="o"><span class="p">(</span><span class="n">i</span><span class="o">&</span><span class="mi">31</span><span class="p">))))</span> <span class="n">primes</span><span class="p">[</span><span class="o">++</span><span class="n">primes</span><span class="p">[</span><span class="mi">0</span><span class="p">]]</span> <span class="o">=</span> <span class="n">nu</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">3</span><span class="p">;</span> <span class="n">j</span> <span class="o"> <span class="n">primes</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">&&</span> <span class="n">primes</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">*</span> <span class="n">nu</span> <span class="o"> <span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">to</span> <span class="o">=</span> <span class="p">(</span><span class="n">nu</span> <span class="o">*</span> <span class="n">primes</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">-</span> <span class="mi">5</span><span class="p">)</span> <span class="o">>></span> <span class="mi">1</span><span class="p">;</span>
            <span class="n">to</span> <span class="o">-=</span> <span class="n">to</span><span class="o">/</span><span class="mi">3</span><span class="p">;</span>
            <span class="n">flags</span><span class="p">[</span><span class="n">to</span><span class="o">>></span><span class="mi">5</span><span class="p">]</span> <span class="o">|=</span> <span class="mi">1</span><span class="o"><span class="p">(</span><span class="n">to</span><span class="o">&</span><span class="mi">31</span><span class="p">);</span>
            <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="p">(</span><span class="n">nu</span> <span class="o">%</span> <span class="n">primes</span><span class="p">[</span><span class="n">j</span><span class="p">]))</span> <span class="k">break</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">nu</span> <span class="o">+=</span> <span class="mi">2</span> <span class="o">+</span> <span class="p">((</span><span class="n">i</span><span class="o">&</span><span class="mi">1</span><span class="p">)</span> <span class="o"> <span class="mi">1</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="n">primes</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="kt">clock_t</span> <span class="n">t</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">"%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">get_prime</span><span class="p">());</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">"Time:%f</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="mf">1.0</span> <span class="o">*</span> <span class="p">(</span><span class="n">clock</span><span class="p">()</span> <span class="o">-</span> <span class="n">t</span><span class="p">)</span> <span class="o">/</span> <span class="n">CLOCKS_PER_SEC</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">primes</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o"> <span class="mi">100</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
      <span class="n">printf</span><span class="p">(</span><span class="s">"%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">primes</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</span></span></span></span></span></span></span></code>
【多种方法比较，长文慎入】

看到各位大神用各种语言写的代码，我这个外行人也跃跃欲试了。
鉴于大家已经给出了C，C++，Python，Mathmatica等的实现过程，那我就用Java吧。

我不会流氓地直接用各种Prime函数（那样对问题讨论毫无意义），还是给出完整实现过程吧。
算法一般，还有待改进，欢迎各位大神指正：

我用的是筛法，稍稍做了优化（把偶数单独列出来筛），代码如下：


1、初始版代码：
<code class="language-java"><span class="kd">class</span> <span class="nc">Prime</span><span class="o">{</span>	
	<span class="kd">public</span> <span class="kd">static</span> <span class="kt">int</span> <span class="nf">calculateNumber</span><span class="o">(</span><span class="kt">int</span> <span class="n">Nmax</span><span class="o">){</span>
		<span class="kt">boolean</span><span class="o">[]</span> <span class="n">isPrime</span><span class="o">=</span><span class="k">new</span> <span class="kt">boolean</span><span class="o">[</span><span class="n">Nmax</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>		
		<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">3</span><span class="o">;</span><span class="n">i</span><span class="o"><span class="n">Nmax</span><span class="o">;</span><span class="n">i</span><span class="o">+=</span><span class="mi">2</span><span class="o">)</span>
			<span class="n">isPrime</span><span class="o">[</span><span class="n">i</span><span class="o">]=</span><span class="kc">true</span><span class="o">;</span>
		<span class="n">isPrime</span><span class="o">[</span><span class="mi">2</span><span class="o">]=</span><span class="kc">true</span><span class="o">;</span>
		<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">3</span><span class="o">;</span><span class="n">i</span><span class="o"><span class="n">Math</span><span class="o">.</span><span class="na">sqrt</span><span class="o">(</span><span class="n">Nmax</span><span class="o">);</span><span class="n">i</span><span class="o">+=</span><span class="mi">2</span><span class="o">){</span>
			<span class="k">if</span><span class="o">(</span><span class="n">isPrime</span><span class="o">[</span><span class="n">i</span><span class="o">]==</span><span class="kc">true</span><span class="o">){</span>
				<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o">*</span><span class="n">i</span><span class="o">;</span><span class="n">j</span><span class="o"><span class="n">Nmax</span><span class="o">;</span><span class="n">j</span><span class="o">+=</span><span class="mi">2</span><span class="o">*</span><span class="n">i</span><span class="o">)</span>
					<span class="n">isPrime</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="kc">false</span><span class="o">;</span>
			<span class="o">}</span>
		<span class="o">}</span>
		<span class="kt">int</span> <span class="n">primeNum</span><span class="o">=</span><span class="mi">0</span><span class="o">;</span>
		<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="o">;</span><span class="n">i</span><span class="o"><span class="n">Nmax</span><span class="o">;</span><span class="n">i</span><span class="o">++){</span>
			<span class="k">if</span><span class="o">(</span><span class="n">isPrime</span><span class="o">[</span><span class="n">i</span><span class="o">]==</span><span class="kc">true</span><span class="o">)</span>
				<span class="n">primeNum</span><span class="o">++;</span>
		<span class="o">}</span>
		<span class="k">return</span> <span class="n">primeNum</span><span class="o">;</span>
	<span class="o">}</span>				
	<span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">){</span>
		<span class="kd">final</span> <span class="kt">int</span> <span class="n">Nmax</span><span class="o">=</span><span class="mi">2000000</span><span class="o">;</span>
		<span class="kt">double</span> <span class="n">startTime</span><span class="o">=</span><span class="n">System</span><span class="o">.</span><span class="na">currentTimeMillis</span><span class="o">();</span>
		<span class="kt">int</span> <span class="n">primeNum</span><span class="o">=</span><span class="n">Prime</span><span class="o">.</span><span class="na">calculateNumber</span><span class="o">(</span><span class="n">Nmax</span><span class="o">);</span>
		<span class="kt">double</span> <span class="n">timeSpent</span><span class="o">=(</span><span class="n">System</span><span class="o">.</span><span class="na">currentTimeMillis</span><span class="o">()-</span><span class="n">startTime</span><span class="o">)/</span><span class="mi">1000</span><span class="o">;</span>
		<span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="s">"The prime numbers from 1 to "</span><span class="o">+</span><span class="n">Nmax</span><span class="o">+</span><span class="s">" is "</span><span class="o">+</span><span class="n">primeNum</span><span class="o">);</span>
		<span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="s">"Time spent : "</span><span class="o">+</span><span class="n">timeSpent</span><span class="o">+</span><span class="s">" s"</span><span class="o">);</span>
	<span class="o">}</span>
<span class="o">}</span>
</span></span></span></span></code>
如果题主希望得到的答案仅限于筛法，那基本上线性筛从复杂度上已经是最优的了，只剩下各种优化了。特别是如果要死扣最后那么点性能，就必然是面向体系结构的优化了，比如多线程优化、根据intel的体系结构如何选择各类指令的分布、用类似prefetch之类的指令降低存储器访问延迟等等。

至于算法层面，从标题来看只是求质数个数，而并不需要枚举所有质数。于是存在比线性更优的算法，可以参考：素数计数函数。其时间复杂度为O(x^(2/3)/log(x))，空间复杂度为O(x^(1/3)log(x)^2)
具体代码实现可以围观：kimwalisch/primecount · GitHub 。

当然最后运行时间对于两百万这个“小”数据基本是可以忽略不计的（如何编程最快速度求出两百万以内素数个数（不限语言和算法）？如何编程最快速度求出两百万以内素数个数（不限语言和算法）？ 如何编程最快速度求出两百万以内素数个数（不限语言和算法）？Mathematica可以在0.012001秒解出来。 quartergeek.com/sieve-p
线性筛法 我来终结此问题。
计算素数个数被数学家和ACMer玩烂了，没啥优化的空间了。
用C语言，计算200万以内素数个数，100次实验取平均
用埃氏筛法，0.035620 seconds
用欧拉筛法，0.025630 seconds
计算1亿以内素数个数，10次实验取平均
用埃氏筛法，2.890600 seconds
用欧拉筛法，1.473400 seconds
运行机器：32位XP
如何编程最快速度求出两百万以内素数个数（不限语言和算法）？
<code class="language-cpp"><span class="cp">#include <math.h></math.h></span>
<span class="cp">#include <stdio.h></stdio.h></span>
<span class="cp">#include <string.h></string.h></span>
<span class="cp">#include <time.h></time.h></span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">N</span> <span class="o">=</span> <span class="mi">2000000</span><span class="p">;</span>
<span class="kt">bool</span> <span class="n">b</span><span class="p">[</span><span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">c</span><span class="p">[</span><span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">];</span>
<span class="kt">void</span> <span class="nf">Era_select</span><span class="p">(){</span> <span class="c1">// Eratosthenes</span>
	<span class="n">memset</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
	<span class="kt">int</span> <span class="n">q</span> <span class="o">=</span> <span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="n">sqrt</span><span class="p">(</span><span class="n">N</span><span class="p">);</span>
	<span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
	<span class="k">for</span> <span class="p">(</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o"><span class="n">q</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span> <span class="p">){</span>
		<span class="k">if</span> <span class="p">(</span> <span class="o">!</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="p">){</span>
			<span class="k">for</span> <span class="p">(</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o"><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o"><span class="n">N</span><span class="p">;</span> <span class="n">j</span><span class="o">+=</span><span class="n">i</span> <span class="p">){</span>
				<span class="n">b</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
			<span class="p">}</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="k">for</span> <span class="p">(</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o"><span class="n">N</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span> <span class="p">){</span>
		<span class="k">if</span> <span class="p">(</span> <span class="o">!</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="p">){</span>
			<span class="o">++</span><span class="n">cnt</span><span class="p">;</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="c1">//printf("%d\n", cnt);</span>
<span class="p">}</span>
<span class="kt">void</span> <span class="nf">Euler_select</span><span class="p">(){</span>
	<span class="n">memset</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">N</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
	<span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">t</span><span class="p">;</span>
	<span class="k">for</span> <span class="p">(</span> <span class="n">i</span><span class="o">=</span><span class="mi">2</span><span class="p">;</span> <span class="n">i</span><span class="o"><span class="n">N</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span> <span class="p">){</span>
		<span class="k">if</span> <span class="p">(</span> <span class="o">!</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="p">){</span>
			<span class="n">c</span><span class="p">[</span><span class="n">cnt</span><span class="o">++</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
		<span class="p">}</span>
		<span class="k">for</span> <span class="p">(</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o"><span class="n">cnt</span><span class="p">;</span> <span class="o">++</span><span class="n">j</span> <span class="p">){</span>
			<span class="n">t</span> <span class="o">=</span> <span class="n">i</span><span class="o">*</span><span class="n">c</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
			<span class="k">if</span> <span class="p">(</span> <span class="n">t</span> <span class="o">></span> <span class="n">N</span> <span class="p">){</span>
				<span class="k">break</span><span class="p">;</span>
			<span class="p">}</span>
			<span class="n">b</span><span class="p">[</span><span class="n">t</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
			<span class="k">if</span> <span class="p">(</span> <span class="n">i</span><span class="o">%</span><span class="n">c</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span> <span class="p">){</span>
				<span class="k">break</span><span class="p">;</span>
			<span class="p">}</span>
		<span class="p">}</span>
	<span class="p">}</span>
	<span class="c1">//printf("%d\n", cnt);</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
	<span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">num</span><span class="o">=</span><span class="mi">100</span><span class="p">;</span>
	<span class="kt">clock_t</span> <span class="n">start</span><span class="p">;</span>
	<span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
	<span class="k">for</span> <span class="p">(</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o"><span class="n">num</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span> <span class="p">){</span>
		<span class="n">Era_select</span><span class="p">();</span>
	<span class="p">}</span>
	<span class="n">printf</span><span class="p">(</span><span class="s">"%lf seconds</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="p">(</span><span class="kt">double</span><span class="p">)(</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="p">)</span> <span class="o">/</span> <span class="n">CLOCKS_PER_SEC</span> <span class="o">/</span> <span class="n">num</span><span class="p">);</span>
	<span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
	<span class="k">for</span> <span class="p">(</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o"><span class="n">num</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span> <span class="p">){</span>
		<span class="n">Euler_select</span><span class="p">();</span>
	<span class="p">}</span>
	<span class="n">printf</span><span class="p">(</span><span class="s">"%lf seconds</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="p">(</span><span class="kt">double</span><span class="p">)(</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="p">)</span> <span class="o">/</span> <span class="n">CLOCKS_PER_SEC</span> <span class="o">/</span> <span class="n">num</span><span class="p">);</span>
	<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</span></span></span></span></span></span></span></span></code>
stackoverflow上有个关于用python求解最快算法的讨论（optimization），如果用纯python语言的话，最快的算法是下面这个：
<code class="language-python"><span class="k">def</span> <span class="nf">rwh_primes2</span><span class="p">(</span><span class="n">n</span> <span class="o">=</span> <span class="mi">10</span><span class="o">**</span><span class="mi">6</span><span class="p">):</span>
    <span class="c"># http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188</span>
    <span class="sd">""" Input n>=6, Returns a list of primes, 2 
    <span class="n">correction</span> <span class="o">=</span> <span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">6</span><span class="o">></span><span class="mi">1</span><span class="p">)</span>
    <span class="n">n</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">:</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">:</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">:</span><span class="n">n</span><span class="o">+</span><span class="mi">4</span><span class="p">,</span><span class="mi">3</span><span class="p">:</span><span class="n">n</span><span class="o">+</span><span class="mi">3</span><span class="p">,</span><span class="mi">4</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="mi">5</span><span class="p">:</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">}[</span><span class="n">n</span><span class="o">%</span><span class="mi">6</span><span class="p">]</span>
    <span class="n">sieve</span> <span class="o">=</span> <span class="p">[</span><span class="bp">True</span><span class="p">]</span> <span class="o">*</span> <span class="p">(</span><span class="n">n</span><span class="o">/</span><span class="mi">3</span><span class="p">)</span>
    <span class="n">sieve</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="bp">False</span>
    <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="nb">int</span><span class="p">(</span><span class="n">n</span><span class="o">**</span><span class="mf">0.5</span><span class="p">)</span><span class="o">/</span><span class="mi">3</span><span class="o">+</span><span class="mi">1</span><span class="p">):</span>
      <span class="k">if</span> <span class="n">sieve</span><span class="p">[</span><span class="n">i</span><span class="p">]:</span>
        <span class="n">k</span><span class="o">=</span><span class="mi">3</span><span class="o">*</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span>
        <span class="n">sieve</span><span class="p">[</span>      <span class="p">((</span><span class="n">k</span><span class="o">*</span><span class="n">k</span><span class="p">)</span><span class="o">/</span><span class="mi">3</span><span class="p">)</span>      <span class="p">::</span><span class="mi">2</span><span class="o">*</span><span class="n">k</span><span class="p">]</span><span class="o">=</span><span class="p">[</span><span class="bp">False</span><span class="p">]</span><span class="o">*</span><span class="p">((</span><span class="n">n</span><span class="o">/</span><span class="mi">6</span><span class="o">-</span><span class="p">(</span><span class="n">k</span><span class="o">*</span><span class="n">k</span><span class="p">)</span><span class="o">/</span><span class="mi">6</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span>
        <span class="n">sieve</span><span class="p">[(</span><span class="n">k</span><span class="o">*</span><span class="n">k</span><span class="o">+</span><span class="mi">4</span><span class="o">*</span><span class="n">k</span><span class="o">-</span><span class="mi">2</span><span class="o">*</span><span class="n">k</span><span class="o">*</span><span class="p">(</span><span class="n">i</span><span class="o">&</span><span class="mi">1</span><span class="p">))</span><span class="o">/</span><span class="mi">3</span><span class="p">::</span><span class="mi">2</span><span class="o">*</span><span class="n">k</span><span class="p">]</span><span class="o">=</span><span class="p">[</span><span class="bp">False</span><span class="p">]</span><span class="o">*</span><span class="p">((</span><span class="n">n</span><span class="o">/</span><span class="mi">6</span><span class="o">-</span><span class="p">(</span><span class="n">k</span><span class="o">*</span><span class="n">k</span><span class="o">+</span><span class="mi">4</span><span class="o">*</span><span class="n">k</span><span class="o">-</span><span class="mi">2</span><span class="o">*</span><span class="n">k</span><span class="o">*</span><span class="p">(</span><span class="n">i</span><span class="o">&</span><span class="mi">1</span><span class="p">))</span><span class="o">/</span><span class="mi">6</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="n">k</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span>
    <span class="k">return</span> <span class="p">[</span><span class="mi">2</span><span class="p">,</span><span class="mi">3</span><span class="p">]</span> <span class="o">+</span> <span class="p">[</span><span class="mi">3</span><span class="o">*</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="o">|</span><span class="mi">1</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="o">/</span><span class="mi">3</span><span class="o">-</span><span class="n">correction</span><span class="p">)</span> <span class="k">if</span> <span class="n">sieve</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span>
</span></code>
很多人说我是喷子，我不同意

对于治病救人，我有时候有不同的理解，这很正常。
看到有人在吃屎，安全的做法是告诉他慢慢吃别噎着，加点油盐酱醋味精啥的，再端碗鸡汤，然后皆大欢喜，大家都很高兴。
虽然我倡导diversity，但我对这种行为异常鄙夷，我认为，你他妈应该立即打断啊。。。（当然，我知道有人是嗜粪的，所以因为我每次都打断所以有时候我也会犯错，但这种情况还是罕见的）


如果不是我必须表现得礼貌，我会说你写的这些东西还不如一坨屎
  • 这是一段根本没法运行的代码，whese is is_prime()???
  • 100000用1e6，我不知道你是什么心态？如果装逼，则可以叉出去了，如果不知道可以直接用200000.....尼玛32位数4294967296是常识吧？更应该叉出去了
  • 乱取名字，竟敢覆盖list，真坑爹
  • 好好的math.sqrt不用，用什么**0.5，什么心态
  • 你那么喜欢所谓“黑科技”优化，为啥不用xrange？
  • 乱用列表推倒，列表没推倒，你自己先倒了
  • 你那么喜欢省代码行数讨厌回车，我推荐你用c语言，用那个可以写成一行
  • 哪有这样写python的？
  • 你觉得跑了21秒的程序有必要写清楚型号配置吗？
  • 如果不是我必须表现得礼貌，我会问你觉得这种垃圾有必要双配置对比吗？
  • 你们可以说他不懂，但这种眼高手低，搞两个名词，乱来一气的做法，跟《小时代》受众在性质上也差不离，人家郭敬明的粉丝也不懂啦

如果你随便玩玩，忽略这些话
如果想好好学，那么建议摆正心态，脚踏实地，不要走火入魔，误入歧途。想要成功，要牢记3点，1是切忌南辕北辙，2是不能说太多， 如果不要求准确值的话，用估算好了，x/ln(x)

以前为了算某个群号，曾经计算了八千万以内的素数，花了两秒钟。群里有个人0.2秒，觉得很牛逼，始终没明白是怎么做的。


我的做法很简单，给出八千万个bool（其实可以去掉偶数）。一开始拿出2，把2的倍数都true了。下一个false的是3，把3的倍数都true了。下一个false的是5，把5的倍数都true了。一只做到完。

陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
上一篇：关于 python gevent 架框 作为 TCP服务器 的 代码问题 ， 每个 socket 的 消息 接收 是否有使用 事件监听回调的方法呢？下一篇：为什么现在新出的互联网站点大多采用 Python 或者 Ruby ？

相關文章

看更多