如何筛选出 10,000 以内的所有质数？

再来问一个，如何筛选出 10,000 以内的质数，任何方法都可以，当然是越简洁越好。

素数筛选法

这个用筛法啊，一种ACM算法
先删掉偶数，在将2,3,5等质数的倍数筛掉，剩下的就是质数了

可以看这里 python执行效率疑问找素数用筛法比试除法效率高很多。

primes 1 10000

请记得安装「bsd-games」软件包。

通常都是通过打表再来调用的

/*
遇到素数需要打表时，先估算素数的个数：
num = n / lnx;
num为大概数字，越大误差越小（只是估计，用于估算素数表数组大小）
这个打表法效率貌似很高，网上说几乎达到了线性时间（不知道是真是假=。=）
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
int n;
bool visit[10100000];
int prime[10000000];


void init_prim()
{
    memset(visit, true, sizeof(visit));
    int num = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (visit[i] == true)
        {
            num++;
            prime[num] = i;
        }
        for (int j = 1; ((j <= num) && (i * prime[j] <= n));  ++j)
        {
            visit[i * prime[j]] = false;
            if (i % prime[j] == 0) break; //点睛之笔
        }
    }
}

int main()
{
    memset(prime, 0, sizeof(prime));
    int count = 0;
    cin>>n;
    init_prim();
    for(int i = 0; i <= n; ++i)
        if(prime[i])
        {
            cout<<prime[i]<<" ";
            count++;
        }
        cout<<endl;
        cout<<"素数个数为："<<count<<endl;
}

工程上，预先打好表，需要的时候直接加载

#include<cstdio>
#include<cmath>
int main(){
int n=4;
bool iszhi;
int zhi[2000];
int sqr=0;
zhi[1]=2;
zhi[2]=3;
zhi[3]=5;
zhi[4]=7;
for (int i=8;i<=10000;i++) {
    iszhi=true;
    sqr=floor(sqrt(i))+1;
    for(int j=1;j<=n;j++){
        if(zhi[j]<sqr){
            if (i%zhi[j]==0){
                iszhi=false;
                break;
            };
        }else{
            break;
        };
    };
    if (iszhi==true) {
        zhi[n+1]=i;
        n++;
    };
};
for(int k=1;k<=n;k++){
    printf("%d\n",zhi[k]);
};
printf("共%d个质数\n",n);
return 1;
}

primes :: [Integer]
primes = sieve [2..]
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

复制一个 Haskell 的来, 取数字时候按下边取:
http://stackoverflow.com/questions/3596502/lazy-list-of-prime-numbers

takeWhile (<1000) primes

给你个one-liner：

[[filter(None, (s.__setitem__(1,0), [[s.__setitem__(j,0) for  j in xrange(i*i, n+1, i)] for  i in xrange(2, int(__import__("math").sqrt(n)) + 1)], s)[2]) for s in (list(range(n+1)),)][0] for n in [10000]][0]

我好无聊…………

@jiyinyiyong

takeWhile (<10000) $ Data.List.nubBy (\x y -> mod x y == 0) [2,3..]

列出2~10000的所有數字，先把2的倍數刪掉，再刪掉3的。。。刪掉5的，以此類推。。。

http://blog.csdn.net/program_think/article/details/7032600

厄拉多塞筛法：一个不在筛上的数字就是质数，而在筛上的数字是合数：给每个合数记录它的因子，用数字+因子放进筛子。

(def primes
  (concat
    [2 3 5 7]
    (lazy-seq
      (let [primes-from
            (fn primes-from [n [f & r]]
              (if (some #(zero? (rem n %))
                        (take-while #(<= (* % %) n) primes))
                (recur (+ n f) r)
                (lazy-seq (cons n (primes-from (+ n f) r)))))
            wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2
                          6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6
                          2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]
        (primes-from 11 wheel)))))

这个是优化过的无穷序列的质数序列的 clojure 语言程序。在我的电脑上，初次运行 10000次 10000以下质数寻找仅需要2.53毫秒。

流氓做法：
从下载到1000000内质数（http://www.doc88.com/p-905280735187.html），然后每个数一行，写道文本文件里。

用的时候，需要多少个数字，直接head到对应行数就行了（囧），速度绝对牛逼，堪称所有方法最快。
（head用法http://blog.sina.com.cn/s/blog_6b7bda7f0100luhp.html）

filter(lambda x:not[x%i for i in range(2,x) if x%i==0],range(2,10000))
虽然比较慢但是挺短的不是吗233

【热门文章】