埃拉托斯特尼筛法 的思想是，我们将自然数集合如果按照素数的顺序进行"筛“(去掉含素数因子的数)，那么得到的是素数集合，它在算法上就是, 准备一个从2开始的素数集合，筛自然数，之后每得个素数，放入集合里作为筛选因子，以下是各语言该算法的实现，排名按代码长短 //java:
2 public class main {
3 public static class PGen{
4 List<Integer> mList = new ArrayList<Integer>();
5 Integer mTestInt;
6 {
7 mList.add(2);mList.add(3);
8 mTestInt = 5;
9 }
10
11 public Boolean iter(){
12 Integer lim = (int)Math.floor(Math.sqrt(mTestInt) );
13 for(Integer p:mList){
14 if(mTestInt%p == 0)return false;
15 if(p>lim)break;
16 }
17 return true;
18 }
19
20 public Integer next(){
21 for(;!iter();mTestInt=mTestInt+2 ){}
22 mList.add(mTestInt);mTestInt+=2;
23 return mTestInt;
24 }
25
26 int idx(int i){
27 while(mList.size()<=i){
28 next();
29 }
30 return mTestInt;
31 }
32
33 void Show(int i){
34 idx(i);
35 for(Integer p:mList){
36 System.out.println(p);
37 }
38 }
39 }
40 public static void main(String[] args) {
41 PGen pl = new PGen();
42 pl.Show(100);
43 }
44 }
//C++:
2
3 struct st_p{
4 std::vector<int> m_p;
5 st_p& init(){m_p.push_back(2);m_p.push_back(3); return *this;}
6 st_p& gen_n(int n){
7 for(int i = 5; m_p.size()!=n; i=i+2){
8 if(is_p(i) )
9 m_p.push_back(i);
10 }
11 return *this;
12 }
13 bool is_p(int n){
14 int l = sqrt(n)+1;
15 for(int i = 0; i<m_p.size(); ++i){
16 int p = m_p[i];
17 if(p>l) break;
18 if(n%p == 0) return false;
19 }
20 return true;
21 }
22 st_p& show(){
23 for(auto v:m_p){
24 printf("%d, ", v);
25 }
26 return *this;
27 }
28 };
29 int _tmain(int argc, _TCHAR* argv[]){
30 st_p().init().gen_n(20).show();return 0;
32 }
-- lua:
2
3 plist = {2}
4
5 isP = function(n)
6 lim = math.floor(math.sqrt(n) )
7 for _, p in ipairs(plist) do
8 if n%p == 0 then return false end
9 if p>lim then return true end
10 end
11 return true;
12 end
13
14 function pgen()
15 return coroutine.wrap(function ()
16 n = 3
17 while true do
18 if isP(n) then table.insert(plist, n);coroutine.yield(n); end
19 n = n+2
20 end
21 end)
22 end
23 k = pgen()
24 for i = 0, 100 do print (k() ) end
//scala:
2
2 import scala.collection.immutable.Stream
3
4 object Sieve extends Application {
5 val prims = Stream.cons(2, checkfrom(3));
6
7 def checkfrom(n: Int):Stream[Int] ={
8 val testps = prims.takeWhile(_ <= math.floor(math.sqrt(n)).toInt);
9 val res = testps.foldLeft(true){(acc, e)=>(n%e != 0)&&acc}
10 if(res) Stream.cons(n, checkfrom(n+2) )
11 else checkfrom(n+2);
12 }
13
14 System.out.println(prims.take(100).toList)
15 };
1 --haskell:
2 prims = 2:(checkfrom 3)
3 where checkfrom iter =
4 let pc = floor.sqrt.fromInteger $ iter
5 in if and $ map ((/=0).(mod iter) ) (take pc plist1)
6 then iter:(checkfrom (iter+2) )
7 else (checkfrom (iter+2) )
8
9 main = putStrLn $ show $ take 100 prims
可以看到：
1. java和c++表达是相似的，你可以精确地表达算法
2. lua和python 是相似的，用到了内置数据结构和生成器
3. scala和 haskell是相似的，lambda, lazy list
4. 表达能力强的语言可以实现较弱语言的表达(废话)，反之不然