社群
學習
工具庫
AI工具
休閒
搜尋
繁体中文
目錄
回复内容：
首頁 後端開發 Python教學 如何编程最快速度求出两百万以内素数个数（不限语言和算法）？

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

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

当然最后运行时间对于两百万这个“小”数据基本是可以忽略不计的（< 10 ms），甚至装载这软件用到的运行库文件都不止这么久，但对于上亿甚至更大的数，相比筛法的优势是很明显的。 如何编程最快速度求出两百万以内素数个数（不限语言和算法）？如何编程最快速度求出两百万以内素数个数（不限语言和算法）？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
如何编程最快速度求出两百万以内素数个数（不限语言和算法）？
<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

Undresser.AI Undress

人工智慧驅動的應用程序，用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！

顯示更多

熱門文章

Windows 11 KB5054979中的新功能以及如何解決更新問題
3 週前 By DDD
如何修復KB5055523無法在Windows 11中安裝？
2 週前 By DDD
Inzoi：如何申請學校和大學
3 週前 By DDD
如何修復KB5055518無法在Windows 10中安裝？
2 週前 By DDD
Roblox：Dead Rails - 如何召喚和擊敗Nikola Tesla
4 週前 By 尊渡假赌尊渡假赌尊渡假赌
顯示更多

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版，非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

顯示更多

熱門話題

gmail信箱登陸入口在哪裡
7828
15
Java教學
1648
14
CakePHP 教程
1402
52
Laravel 教程
1300
25
PHP教程
1239
29
顯示更多
Related knowledge
如何解決Linux終端中查看Python版本時遇到的權限問題？ 如何解決Linux終端中查看Python版本時遇到的權限問題？ Apr 01, 2025 pm 05:09 PM

Linux終端中查看Python版本時遇到權限問題的解決方法當你在Linux終端中嘗試查看Python的版本時，輸入python...

如何在使用 Fiddler Everywhere 進行中間人讀取時避免被瀏覽器檢測到？ 如何在使用 Fiddler Everywhere 進行中間人讀取時避免被瀏覽器檢測到？ Apr 02, 2025 am 07:15 AM

使用FiddlerEverywhere進行中間人讀取時如何避免被檢測到當你使用FiddlerEverywhere...

在Python中如何高效地將一個DataFrame的整列複製到另一個結構不同的DataFrame中？ 在Python中如何高效地將一個DataFrame的整列複製到另一個結構不同的DataFrame中？ Apr 01, 2025 pm 11:15 PM

在使用Python的pandas庫時，如何在兩個結構不同的DataFrame之間進行整列複製是一個常見的問題。假設我們有兩個Dat...

Uvicorn是如何在沒有serve_forever()的情況下持續監聽HTTP請求的？ Uvicorn是如何在沒有serve_forever()的情況下持續監聽HTTP請求的？ Apr 01, 2025 pm 10:51 PM

Uvicorn是如何持續監聽HTTP請求的？ Uvicorn是一個基於ASGI的輕量級Web服務器，其核心功能之一便是監聽HTTP請求並進�...

如何在10小時內通過項目和問題驅動的方式教計算機小白編程基礎？ 如何在10小時內通過項目和問題驅動的方式教計算機小白編程基礎？ Apr 02, 2025 am 07:18 AM

如何在10小時內教計算機小白編程基礎？如果你只有10個小時來教計算機小白一些編程知識，你會選擇教些什麼�...

FastAPI中如何處理逗號分隔的列表查詢參數？ FastAPI中如何處理逗號分隔的列表查詢參數？ Apr 02, 2025 am 06:51 AM

fastapi ...

在Linux終端中使用python --version命令時如何解決權限問題？ 在Linux終端中使用python --version命令時如何解決權限問題？ Apr 02, 2025 am 06:36 AM

Linux終端中使用python...

如何繞過Investing.com的反爬蟲機制獲取新聞數據？ 如何繞過Investing.com的反爬蟲機制獲取新聞數據？ Apr 02, 2025 am 07:03 AM

攻克Investing.com的反爬蟲策略許多人嘗試爬取Investing.com（https://cn.investing.com/news/latest-news）的新聞數據時，常常�...

See all articles