Community Learn Tools Library Leisure
search
English
Home > Backend Development > Python Tutorial > body text

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

WBOY
Release： 2016-06-06 16:22:47
Original
2243 people have browsed it

回复内容：

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>
Copy after login
【多种方法比较，长文慎入】

看到各位大神用各种语言写的代码，我这个外行人也跃跃欲试了。
鉴于大家已经给出了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>
Copy after login
如果题主希望得到的答案仅限于筛法，那基本上线性筛从复杂度上已经是最优的了，只剩下各种优化了。特别是如果要死扣最后那么点性能，就必然是面向体系结构的优化了，比如多线程优化、根据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>
Copy after login
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>
Copy after login
很多人说我是喷子，我不同意

对于治病救人，我有时候有不同的理解，这很正常。
看到有人在吃屎，安全的做法是告诉他慢慢吃别噎着，加点油盐酱醋味精啥的，再端碗鸡汤，然后皆大欢喜，大家都很高兴。
虽然我倡导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了。一只做到完。

source：php.cn
Previous article：关于 python gevent 架框 作为 TCP服务器 的 代码问题 ， 每个 socket 的 消息 接收 是否有使用 事件监听回调的方法呢？ Next article：为什么现在新出的互联网站点大多采用 Python 或者 Ruby ？
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
function_exists() cannot determine the custom function Function test () {return true;} if (function_exists ('test')) {echo "test is function...
From 2024-04-29 11:01:01
0
2
1876
How to display the mobile version of Google Chrome Hello teacher, how can I change Google Chrome into a mobile version?
From 2024-04-23 00:22:19
0
10
2042
The child window operates the parent window, but the output does not respond. The first two sentences are executable, but the last sentence cannot be implemented.
From 2024-04-19 15:37:47
0
1
1719
There is no output in the parent window document.onclick = function(){ window.opener.document.write('I am the output of the child ...
From 2024-04-18 23:52:34
0
1
1621
Where is the courseware about CSS mind mapping? Courseware
From 2024-04-16 10:10:18
0
0
1633
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template