如何编程最快速度求出两百万以内素数个数（不限语言和算法）？-파이썬 튜토리얼-php.cn

집

백엔드 개발

파이썬 튜토리얼

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 06, 2016 pm 04:22 PM

回复内容：

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

<span class="cp">#include <stdio.h></span>
<span class="cp">#include <time.h></span>
<span class="cp">#include <string.h></span>
<span class="cp">#include <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> <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><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> <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> <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><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> <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> <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>

【多种方法比较，长文慎入】

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

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

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

1、初始版代码：

<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><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><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><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><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>

如果题主希望得到的答案仅限于筛法，那基本上线性筛从复杂度上已经是最优的了，只剩下各种优化了。特别是如果要死扣最后那么点性能，就必然是面向体系结构的优化了，比如多线程优化、根据intel的体系结构如何选择各类指令的分布、用类似prefetch之类的指令降低存储器访问延迟等等。

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

当然最后运行时间对于两百万这个“小”数据基本是可以忽略不计的（

Mathematica可以在0.012001秒解出来。 http://quartergeek.com/sieve-prime-in-linear-time/
线性筛法我来终结此问题。
计算素数个数被数学家和ACMer玩烂了，没啥优化的空间了。
用C语言，计算200万以内素数个数，100次实验取平均
用埃氏筛法，0.035620 seconds
用欧拉筛法，0.025630 seconds
计算1亿以内素数个数，10次实验取平均
用埃氏筛法，2.890600 seconds
用欧拉筛法，1.473400 seconds
运行机器：32位XP

<span class="cp">#include <math.h></span>
<span class="cp">#include <stdio.h></span>
<span class="cp">#include <string.h></span>
<span class="cp">#include <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><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><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o"><=</span><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><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><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><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><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><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>

stackoverflow上有个关于用python求解最快算法的讨论（optimization），如果用纯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 <= p < n """</span>
    <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>

很多人说我是喷子，我不同意

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

핫 AI 도구

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

AI 옷 제거제

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

맨티스BT

Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.

mPDF

mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.