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

Jadual Kandungan

回复内容：

Rumah

pembangunan bahagian belakang

Tutorial Python

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

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>

Salin selepas log masuk

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

看到各位大神用各种语言写的代码，我这个外行人也跃跃欲试了。
鉴于大家已经给出了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>

Salin selepas log masuk

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

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

当然最后运行时间对于两百万这个“小”数据基本是可以忽略不计的（< 10 ms），甚至装载这软件用到的运行库文件都不止这么久，但对于上亿甚至更大的数，相比筛法的优势是很明显的。

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>

Salin selepas log masuk

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>

Salin selepas log masuk

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

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

Kenyataan Laman Web ini

Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

Menjana ai hentai secara percuma.

Tunjukkan Lagi

Artikel Panas

Assassin's Creed Shadows: Penyelesaian Riddle Seashell

3 minggu yang lalu By DDD

Apa yang Baru di Windows 11 KB5054979 & Cara Memperbaiki Masalah Kemas Kini

2 minggu yang lalu By DDD

Di mana untuk mencari kad kunci kawalan kren di atomfall

3 minggu yang lalu By DDD

Penjimatan di R.E.P.O. Dijelaskan (dan simpan fail)

1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Assassin's Creed Shadows - Cara Mencari Orang Panda

4 minggu yang lalu By DDD

Tunjukkan Lagi

Alat panas

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Tunjukkan Lagi

Topik panas

Di manakah pintu masuk log masuk untuk e-mel gmail?

7569

Tutorial CakePHP

1386

Apakah format nama akaun stim

kunci pengaktifan win11 kekal

Sambungan NYT menunjukkan dan jawapan

107

Tunjukkan Lagi

Related knowledge

Bagaimana untuk menyelesaikan masalah kebenaran yang dihadapi semasa melihat versi Python di Terminal Linux? Apr 01, 2025 pm 05:09 PM

Penyelesaian kepada Isu Kebenaran Semasa Melihat Versi Python di Terminal Linux Apabila anda cuba melihat versi Python di Terminal Linux, masukkan Python ...

Bagaimana cara menyalin seluruh lajur satu data ke dalam data data lain dengan struktur yang berbeza di Python? Apr 01, 2025 pm 11:15 PM

Apabila menggunakan Perpustakaan Pandas Python, bagaimana untuk menyalin seluruh lajur antara dua data data dengan struktur yang berbeza adalah masalah biasa. Katakan kita mempunyai dua DAT ...

Bagaimana Mengajar Asas Pengaturcaraan Pemula Komputer Dalam Kaedah Projek dan Masalah Dikemukakan Dalam masa 10 Jam? Apr 02, 2025 am 07:18 AM

Bagaimana Mengajar Asas Pengaturcaraan Pemula Komputer Dalam masa 10 jam? Sekiranya anda hanya mempunyai 10 jam untuk mengajar pemula komputer beberapa pengetahuan pengaturcaraan, apa yang akan anda pilih untuk mengajar ...

Bagaimana untuk mengelakkan dikesan oleh penyemak imbas apabila menggunakan fiddler di mana-mana untuk membaca lelaki-dalam-tengah? Apr 02, 2025 am 07:15 AM

Cara mengelakkan dikesan semasa menggunakan fiddlerevery di mana untuk bacaan lelaki-dalam-pertengahan apabila anda menggunakan fiddlerevery di mana ...

Apakah ungkapan biasa? Mar 20, 2025 pm 06:25 PM

Ekspresi biasa adalah alat yang berkuasa untuk memadankan corak dan manipulasi teks dalam pengaturcaraan, meningkatkan kecekapan dalam pemprosesan teks merentasi pelbagai aplikasi.

Bagaimanakah uvicorn terus mendengar permintaan http tanpa serving_forever ()? Apr 01, 2025 pm 10:51 PM

Bagaimanakah Uvicorn terus mendengar permintaan HTTP? Uvicorn adalah pelayan web ringan berdasarkan ASGI. Salah satu fungsi terasnya ialah mendengar permintaan HTTP dan teruskan ...

Apakah beberapa perpustakaan Python yang popular dan kegunaan mereka? Mar 21, 2025 pm 06:46 PM

Artikel ini membincangkan perpustakaan Python yang popular seperti Numpy, Pandas, Matplotlib, Scikit-Learn, Tensorflow, Django, Flask, dan Permintaan, memperincikan kegunaan mereka dalam pengkomputeran saintifik, analisis data, visualisasi, pembelajaran mesin, pembangunan web, dan h

Bagaimana secara dinamik membuat objek melalui rentetan dan panggil kaedahnya dalam Python? Apr 01, 2025 pm 11:18 PM

Di Python, bagaimana untuk membuat objek secara dinamik melalui rentetan dan panggil kaedahnya? Ini adalah keperluan pengaturcaraan yang biasa, terutamanya jika perlu dikonfigurasikan atau dijalankan ...

See all articles