標籤：

如何編程求解 100 以內的質數？

01-03

print prime under 100 Brainf**k impl
&>&>++[&<+++++[&<+++++&>-]&>-]&<&<.&>&>++++[&<+++++ +++&>-]&<.&<+.&>.&>&>&>+++++[&<+++++[&<++++&>-]&>-]
&<&<------&>+++++&<[&>&>&>&>[-]+++[-&>+&>+&<&<]&>&>[-&< &<+&>&>]&>&>+&<&<&<&<&<&<+[[-]&<[-&>+&>+&<&<]&>&>[-&<&<+&>&>]&>
&>[-]&<[-&>+&>+&<&<]&>&>[-&<&<+&>&>]&<&<&<&<[-&>&>&>-&>+&<[&>-
]&>[-&<&<[-&>+&>+&<&<]&>&>[-&<&<+&>&>]&>]&<&<&<&<&<]&>&>[-&>-&>
+&<&<]&>&>[-&<&<+&>&>]+&<[&>-]&>[-&>&>[-]&<]&<&<&<&<&<&<[-&>+
&>+&<&<]&>&>[-&<&<+&>&>]&>&>[-]&<++[-&>+&>+&<&<]&>&>[-&<&<+&>
&>]&<[-&<&<&<-&>&>&>]&<&<&<]&>&>&>&>&>&>[&<&<&<&<&<&<&<[-&>+&>+&<&<] &>&>[-&<&<+&>&>]&>[-]++++++++++&>[-]++++++++++&<&< &<[-&>&>&>-&>+&<[&>-]&>[-&<&<[-&>+&>+&<&<]&>&>[-&<&<+&>&>]&>&>
&>+&>[-]-&<&<&<]&>&>&>+&<&<&<&<&<&<&<&<]&>&>&>&>&>&>&>[++++++++
++++++++++++++++++++++++++++++++++++++++
.[-]]&>++++++++++++++++++++++++++++++++++
++++++++++++++.[-]&<&<&<&<&<&<&<&<&<&<&<.&>&>&>&>&>&>&>&>&>-
]&<&<&<&<&<&<&<++&<--]

Brainf**k大法好

上面的程序也許不太好懂，我們來展開一下：

// 輸出一些特例
&>&>++[&<+++++[&<+++++&>-]&>-]&<&<. // 輸出"2" &>&>++++[&<++++++++&>-]&<. // 輸出空格 &<+. // 輸出"3" &>. // 輸出空格

// 開始循環計算
&> &>&>+++++[&<+++++[&<++++&>-]&>-]&<&<------ // 循環次數：94 &>+++++ // 從5開始逐個判斷
&< [ // 循環直到循環次數為0 &>&>&>&> [-] +++ // 初始化除數為3
[-&>+&>+&<&<]&>&>[-&<&<+&>&>] // 複製一份除數用於計算
&>&> + // 標記是否是質數的flag
&<&<&<&<&<&< + // 進入試除循環 [ // 循環條件見對應的方括弧之前 [-] &< [-&>+&>+&<&<]&>&>[-&<&<+&>&>] // 複製一份被除數用於計算
&>&> [-] &< [-&>+&>+&<&<]&>&>[-&<&<+&>&>] // 複製一份除數（OAO前面那個其實好像沒必要
// 開始計算餘數
&<&<&<&< [ // 循環條件：被除數不為0 - &>&>&> - // 被除數和除數各減1
// 看看下面這行是如何實現分支的？
&>+ &< [&>-] &> [ - // 除數為0
&<&< [-&>+&>+&<&<]&>&>[-&<&<+&>&>] // 就再複製一份除數來
&>
]
&<&<&<&<&< ] &>&> [-&>-&>+&<&<] &>&> [-&<&<+&>&>]
+&< [ &>- ] &> [ - // 被除數和除數同時為0，說明整除
&>&> [-] // 清除質數標記
&< ] &<&<&<&<&<&< [-&>+&>+&<&<]&>&>[-&<&<+&>&>] // 被除數
&>&> [-]
&< ++ // 除數加2 [-&>+&>+&<&<]&>&>[-&<&<+&>&>] // 除數
&< [-&<&<&<-&>&>&>] // 被除數大於除數，循環繼續；否則結束循環
&<&<&< ] // 算完了，列印 &>&>&>&>&>&>
[ // 是質數
&<&<&<&<&<&<&< [-&>+&>+&<&<]&>&>[-&<&<+&>&>] // 複製一份用來計算顯示
// 下面是和之前計算類似的除10操作
&>[-]++++++++++
&>[-]++++++++++
&<&<&< [ - &>&>&> -
&>+ &< [ &>- ] &> [ - // 減一次10
&<&< [-&>+&>+&<&<]&>&>[-&<&<+&>&>]
&>&>&> + // 十位數加1
&> [-]- // 清空個位數，這裡減的1會以循環外面補上
&<&<&< ] &>&>&> + // 個位數+1
&<&<&<&<&<&<&<&< ] // 有十位數則輸出 &>&>&>&>&>&>&> [++++++++++++++++++++++++++++++++++++++++++++++++ . [-]]
// 輸出個位數
&> ++++++++++++++++++++++++++++++++++++++++++++++++ . [-]
// 輸出空格
&<&<&<&<&<&<&<&<&<&<&<.&>&>&>&>&>&>&>&>&>
- // 清除質數flag
]
&<&<&<&<&<&<&< ++ // 被除數加2 &< -- // 循環次數減2 ]

既然這題已經被玩壞了。。。我也要玩。。。

你們那些語言都退下吧！

看我大莎士比亞語言！

Prime Number Computation in Copenhagen.

Romeo, a young man of Verona.
Juliet, a young woman.
Hamlet, a temporary variable from Denmark.
The Ghost, a limiting factor (and by a remarkable coincidence also
Hamlet"s father).

Act I: Interview with the other side.

Scene I: At the last hour before dawn.

[Enter the Ghost and Juliet]

The Ghost:
You pretty little warm thing! Thou art as prompt as the difference
between the square of thyself and your golden hair. Speak your mind.

Juliet:
Listen to your heart!

[Exit the Ghost]

[Enter Romeo]

Juliet:
Thou art as sweet as a sunny summer"s day!

Act II: Determining divisibility.

Scene I: A private conversation.

Juliet:
Art thou more cunning than the Ghost?

Romeo:
If so, let us proceed to scene V.

[Exit Romeo]

[Enter Hamlet]

Juliet:
You are as villainous as the square root of Romeo!

Hamlet:
You are as lovely as a red rose.

Scene II: Questions and the consequences thereof.

Juliet:
Am I better than you?

Hamlet:
If so, let us proceed to scene III.

Juliet:
Is the remainder of the quotient between Romeo and me as good as
nothing?

Hamlet:
If so, let us proceed to scene IV.
Thou art as bold as the sum of thyself and a roman.

Juliet:
Let us return to scene II.

Scene III: Romeo must die!

[Exit Hamlet]

[Enter Romeo]

Juliet:
Open your heart.

[Exit Juliet]

[Enter Hamlet]

Romeo:
Thou art as rotten as the difference between nothing and the sum of a
snotty stinking half-witted hog and a small toad!
Speak your mind!

[Exit Romeo]

[Enter Juliet]

Scene IV: One small dog at a time.

[Exit Hamlet]

[Enter Romeo]

Juliet:
Thou art as handsome as the sum of thyself and my chihuahua!
Let us return to scene I.

Scene V: Fin.

[Exeunt]

好吧我承認我也不知道什麼意思。。。。官網抄的。。。

http://shakespearelang.sourceforge.net/report/shakespeare/#SECTION00092000000000000000

嗯哼。。。

Wireworld 機械圖，可以逐個在七段數碼管里顯示素數。這玩意 Golly 里有對應的 rle，可以直接打開運行（記得調高速度到 10000x）。來源圖中已包含。

對應的「彙編語言」是：

Reg Hex Disassembly

1 001e MOV R0 ,R30 ; set display to 2
2 361f MOV R54,R31 ; initialise mask register for sign bit test
3 2021 MOV R32,R33 ; set candidate prime p=3
4 3c22 MOV R60,R34 ; the trial divisor q is stored in the adder as its
; negative: here it is initialised to -1, i.e. q=1
5 3d23 MOV R61,R35 ; other summand=-2
6 3c3d MOV R60,R61 ; next trial divisor q=q+2
7 3d20 MOV R61,R32 ; move p to adder summand input a, which holds remainder
8 3924 MOV R57,R36 ; for the first time round the loop, set the target
; for the branch if subtraction gives zero to 20: this
; detects the case p==q, which means we have done all
; the trial divisors and p is prime
9 3725 MOV R55,R37 ; if subtraction result non-zero, target is 13
10 383d MOV R56,R61 ; test a-q
11 3f38 MOV R63,R56 ; branch to selected target
12 3d3d MOV R61,R61 ; a-=q
13 3d3d MOV R61,R61 ; a-=q (continuing here if subtraction result not zero)
14 353d MOV R53,R61 ; move a-q to and-not register to check sign
15 3926 MOV R57,R38 ; target is 9 if a-q positive (round subtraction loop
; again)
16 3727 MOV R55,R39 ; else target is 5 (q does not divide p, so try next q)
17 3836 MOV R56,R54 ; test a-q AND 0x8000
18 3f38 MOV R63,R56 ; branch to selected target
19 3928 MOV R57,R40 ; reset target for other branch to 21 (a zero result
; from the subtraction now indicates q properly
; divides p and so p is composite)
20 0020 MOV R0 ,R32 ; p is prime: write it to the display
21 3d20 MOV R61,R32 ; move p to adder
22 3c1e MOV R60,R30 ; other summand=2
23 3f29 MOV R63,R41 ; goto 4 to try new p
24 203d MOV R32,R61 ; p+=2
25 ; unused
26 ; unused
27 ; unused
28 ; unused
29 ; unused
30 0002 ; constant 2
31 7fff ; constant mask for sign bit testing
32 0005 ; current candidate p
33 0003 ; constant 3
34 fffe ; constant -1
35 fffd ; constant -2
36 0014 20 ; branch target: trial divisor q equal to candidate p,
; and hence prime found
37 000d 13 ; branch target: trial divisor q less than candidate p
38 0009 9 ; branch target: more subtractions to do
39 0005 5 ; branch target: next trial divisor q
40 0015 21 ; branch target: subtraction gave zero, so p composite
41 0004 4 ; branch target: next candidate p
42 fffc ; constant -3

各個寄存器讀寫時的行為是：

我嘗試用一行C++11代碼模仿 @大人 的 Python式實現：

copy_if(range(2, 101), ostream_iterator&(cout, " "), [](int x){ return none_of(range(2, x), [x](int y) { return x % y == 0; }); });

這樣比較容易理解：

copy_if( // 複製
range(2, 101), // 數列 { 2, 3, .. 100 } 中的整數
ostream_iterator&(cout, " "), // 至cout（每個輸出後加入空格）
[](int x) { // 僅當對於每個整數x
return none_of( // 沒有一個
range(2, x), // y in { 2, ..., x - 1 }
[x](int y) { // 乎合
return x % y == 0; // y 為 x 的因子
}
);
}
);

-----

為了實現這個函數式實現，C++11不提供range()的功能，需要自行實現一個。完整的程序是這樣的：

#include &
#include &
#include &

using namespace std;

template &
class range_type {
public:
class range_iterator {
public:
typedef T value_type;
typedef T* pointer;
typedef T reference;
typedef ptrdiff_t difference_type;
typedef forward_iterator_tag iterator_category;

range_iterator(T v) : v_(v) {}
T operator*() const { return v_; }
range_iterator operator++() { ++v_; return *this; }
range_iterator operator++(int) { range_iterator copy(*this); ++v_; return copy; }
bool operator==(const range_iterator other) const { return v_ == other.v_; }
bool operator!=(const range_iterator other) const { return v_ != other.v_; }
private:
T v_;
};

range_type(T lower, T upper) : lower_(lower), upper_(upper) {}
range_iterator begin() const { return range_iterator(lower_); }
range_iterator end() const { return range_iterator(upper_); }

private:
T lower_, upper_;
};

template &
range_type& range(T lower, T upper) { return range_type&(lower, upper); }

template &
bool none_of(const Container c, UnaryPredicate pred) { return none_of(c.begin(), c.end(), pred); }

template &
void copy_if(const Container c, DestIterator d, UnaryPredicate pred) { copy_if(c.begin(), c.end(), d, pred); }

int main() {
copy_if(range(2, 101), ostream_iterator&(cout, " "), [](int x){ return none_of(range(2, x), [x](int y) { return x % y == 0; }); });
return 0;
}

另外，因為C++ algorithm標頭檔的函數都使用 begin, end 作為參數，為了把程序寫成一行，我加入了使用container作為參數的none_of()和copy_if()。

相信沒有學生會把這段代碼當功課交吧。

-----

2014/11/10更新：不少評論說了各種「優化」方法。

包括把內循環的範圍從[2, x)降至[2, left lfloor frac{x}{2} ight floor + 1)，或者更好的[2, left lfloor sqrt{x} ight floor + 1)。另外也可以只測試之前的質數是否因子。

我作了一個簡單的測試：

void test(int t, std::vector& p, int n, function& isPrime) {
p.clear();
clock_t start = clock();
copy_if(range(2, n + 1), back_inserter(p), isPrime);
clock_t end = clock();
cout &<&< t &<&< ". " &<&< p.size() &<&< " " &<&< (end - start) * 1000.0 / CLOCKS_PER_SEC &<&< "ms" &<&< endl; } int main() { std::vector& p;
p.reserve(10000);

const int n = 100000;

test(1, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return x % y == 0; }); });
test(2, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return y * 2 &<= x x % y == 0; }); }); test(3, p, n, [](int x) { return none_of(range(2, x / 2 + 1), [x](int y) { return x % y == 0; }); }); test(4, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return y * y &<= x x % y == 0; }); }); test(5, p, n, [](int x) { return none_of(range(2, x), [x](int y) { return y &<= (int)sqrt(x) x % y == 0; }); }); test(6, p, n, [](int x) { return none_of(range(2, (int)sqrt(x) + 1), [x](int y) { return x % y == 0; }); }); test(7, p, n, [p](int x) { return none_of(p, [x](int y) { return x % y == 0; }); }); test(8, p, n, [p](int x) { return none_of(p, [x](int y) { return y * y &<= x x % y == 0; }); }); test(9, p, n, [p](int x) { return none_of(p, [x](int y) { return y &<= (int)sqrt(x) x % y == 0; }); }); test(10, p, n, [p](int x) { for (auto y : p) { if (y &> (int)sqrt(x))
return true;
else if (x % y == 0)
return false;
}
return true;
});

//copy(p, ostream_iterator&(cout, " "));

return 0;
}

為了測試性能，我把n調至100000，並避免輸出字元串的開銷，只把結果寫在vector里。

運行結果：

1. 9592 1564ms
2. 9592 927ms
3. 9592 784ms
4. 9592 569ms
5. 9592 293ms
6. 9592 11ms
7. 9592 159ms
8. 9592 65ms
9. 9592 33ms
10. 9592 4ms

如果能減少範圍，直接改動上界（測試3、6）是較好的。雖然測試5減少了調用sqrt()，但因為仍然需要迭代整個範圍，會比測試6要慢得多。

對於使用之前結果中的質數，測試7比測試6（簡單的開方優化）要慢。但在這情況下，我們不能改變上界（不知道現時已存的質數哪個大於x的開方），測試8和9的結果仍然比測試6要慢。

最後，唯有放棄使用none_of()，才能避免迭代整個範圍，達到這些測試中最優的測試10。

居然比C++還快。

其實Rust也可以這麼玩的，先放一個最基本的

use std::num::Float;
use std::iter::range_inclusive;
fn main() {
const LIMIT: uint = 100;
let result = range_inclusive(2, LIMIT)
.filter(|x| {
range_inclusive(2, (x as f64).sqrt() as uint)
.all(|n| x % n != 0)
}).collect::&&>();

println!("{}", result);
}

如果不需要數組的話，直接for然後輸出會更快一些。

隨手測試，用樓上的大大們的程序測了下

# rustc 0.13.0-nightly (126db549b 2014-12-15 00:07:35 +0000)
./prime 0.01s user 0.00s system 80% cpu 0.009 total

# Rust with -O flag (equivalent to -opt-level=2)
./prime 0.00s user 0.00s system 66% cpu 0.006 total

# ruby 2.0.0p481 (2014-05-08 revision 45883) [universal.x86_64-darwin14]
ruby prime.rb 0.32s user 0.01s system 99% cpu 0.331 total

# Python 3.4.2
python3 prime.py 0.51s user 0.01s system 94% cpu 0.549 total

# CPP with -O2
# (Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn))
./cpp_prime 0.02s user 0.00s system 93% cpu 0.022 total

竟然比C++還快！全部測試在MacBook Pro 2013 Late i5進行，結果可重現！

Rust大法好！！！！！

這個時候當然要祭出正則表達式求素數的版本。

(1 x ++$_) =~ /^1?$|^(11+?)1+$/ || print "$_
" while $_ &< 100

既然有人問原理，那就祭出m67的博文吧：

http://www.matrix67.com/blog/archives/475

0到100而已，你們至於么？口算不就行了？

vector& prime_0_100()
{
return vector&{2,3}; //010 and 011
}

我用 GNU Octave：

primes(100)

順便貼一個 codegolf.stackexchange.com 上的相關問題：code golf - List of primes under a million

x86機器碼:

8b 44 24 04 8b 58 04 53 8b 18 53 8b cc e8 06 00
00 00 83 c4 08 c2 04 00 55 8b ec 83 ec 24 53 56
57 8b 79 04 c7 45 f8 00 00 00 00 6a 0a 89 65 dc
68 25 64 20 00 89 65 e0 68 25 64 00 00 89 65 f0
8d 45 fc 50 ff 75 f0 8b 01 ff d0 8b 4d fc 83 c4
08 8b c1 d1 f9 83 e0 fc 41 83 c0 04 89 4d e8 89
45 f4 c1 e8 02 89 45 ec 2b 65 f4 89 65 e4 33 c9
b8 01 01 01 01 33 d2 89 04 8c 41 3b 4d ec 72 f7
66 89 14 24 b9 02 00 00 00 80 3c 0c 00 72 11 8d
1c 4d 00 00 00 00 88 14 1c 03 d9 3b 5d fc 72 f6
41 3b 4d e8 72 e3 33 f6 39 75 fc 7e 43 8b 45 e4
80 3c 06 00 74 34 56 ff 75 e0 ff d7 8b 5d f8 b8
67 66 66 66 43 83 c4 08 f7 eb 89 5d f8 c1 fa 02
8b c2 c1 e8 1f 03 c2 8d 0c 80 8b c3 03 c9 2b c1
75 08 ff 75 dc ff d7 83 c4 04 46 3b 75 fc 7c bd
03 65 f4 83 c4 0c 5f 5e 5b 8b e5 5d c3 90

原型:

void __stdcall prime_number(void *funcAddrList);

提供運行時函數:

void* funcAddrList[] = { scanf, printf };

輸入n,輸出小於n的質數,可直接運行

////============質數判定對應彙編:============

sub esp, array_size
mov a, esp
//====init begin====
xor ecx, ecx
mov eax, 0x01010101
xor edx, edx
LOOP_INIT1 :
mov[esp + ecx * 0x04], eax
inc ecx

cmp ecx, array_size_by4
jb LOOP_INIT1

mov[esp], dx
//====init end====
//====loop begin====
mov ecx, 2
LOOP_I1 :
cmp[esp + ecx], 0x00
jb LOOP_I2
//prime number:ecx
lea ebx, [ecx * 2]

LOOP_J1 :
mov[esp + ebx], dl
add ebx, ecx
cmp ebx, num
jb LOOP_J1

LOOP_I2 :
inc ecx
cmp ecx, num
_sqrt
jb LOOP_I1

//====loop end====

那些直接用反彙編的太沒節操了,手寫才是浪漫嘛

//============運行方式可見:============

//有哪些編程語言可以做到在程序運行時讀入並執行一段代碼？ - 朱慶喵的回答

C++ 搞 lazy 又不是不能搞：

#include &
#include &
#include &
using namespace ranges::v3::view;

int main()
{
constexpr std::uint32_t kLimit = 100;
constexpr std::uint32_t kStart = 2;
auto result = iota(kStart, kLimit) | remove_if([](auto x) {
return (ranges::count_if(closed_ints(kStart, static_cast&(std::sqrt(x))), [x](auto y) {
return x % y == 0;
})) != 0;
});
for (auto x : result)
std::printf("%u ", x);
}

@羅宸 無限的也不難呀

#include &
#include &
#include &

using namespace ranges::v3::view;

int main()
{
constexpr std::uint32_t kLimit = 100;
constexpr std::uint32_t kStart = 2;
auto result = iota(kStart) | remove_if([](auto x) {
return (ranges::count_if(closed_ints(kStart, static_cast&(std::sqrt(x))), [x](auto y) {
return x % y == 0;
})) != 0;
});
RANGES_FOR(auto x, result | take(kLimit))
std::printf("%u ", x);
}

提供一個 Ruby 版供參考

print (2..100).select {|n| (2..(n + 1) / 2).all? {|d| n % d &>0}}

輸出

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97]

補充

剛才無聊，比較了一下 @Milo Yip 的 C++ 11 版本， @大人 的 Python 版本, 和上面 Ruby 版本的速度 (求 2..10000 內的質數，用命令 time 測試耗費時間)，測試環境 Mid 2013 MacBook Air 13 inch 1.3GHZ Core i5 CPU on Yosemite 10.10. 編譯器解釋器都是 Xcode 6.1 或 Yosemite 自帶的。

下面是結果:

C++ 11 32ms (clang-600.0.54 打開 -O3)
Python 8340ms (Python 2.7.6)
Ruby 357ms (Ruby 2.1.1p76)

C++ 11 在這個任務上比 Ruby 快 10 倍，Ruby 比 Python 快 20 倍。 印象中 Python 比 Ruby 略快的。

再補充: @bhuztez 評論中提出一種更好的 Python 方案

print [x for x in range(2,10001) if all(x%y for y in range(2,(x+2)/2))]

這種方案運行時間為 590ms ，經過 @王維捷 進一步提示，把 range 替換成 xrange 後速度提升為 369ms , 基本上和 Ruby 版本持平。 我估計 @大人 版本的效率問題主要是冗餘的列表和容器操作造成的。

初步結論:

1. 在演算法等價的情況下，C++ 實現大約比 Python 和 Ruby 實現快一個數量級。

2. 腳本語言中的非優化實現，很容易進一步造成一個數量級以上的性能差距。

Haskell再來一發。 既然要完爆各種阿貓阿狗語言，就來得徹底一點好了。。

實現是下面這樣，除了isPrime里幾個裝B的函數組合稍微不直觀一點，其它代碼直白得接近白話。

isPrime x = all ((/= 0) . (x `mod`)) $ takeWhile ((&<= x) . (^ 2)) primes primes = 2 : filter isPrime [3..]

請留意上面實現的primes就是個無窮的素數列表（難道不應該就是這樣么，你們拿出來的那些都是啥@#@#￥%%……）

然後拿所有小於100的素數就是：

takeWhile (&< 100) primes

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

拿前100個素數就是：

take 100 primes

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71.. 521,523,541]

前100個孿生素數對就是：

primePairs = filter ((a, b) -&> a + 2 == b) $ zip primes (tail primes)
take 100 primePairs

[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43) .. (3767,3769),(3821,3823)]

完整的代碼（包括性能測試報告）在這裡：my-utils.hs/primes2.hs at master · luochen1990/my-utils.hs · GitHub

當然這個實現是權衡了 實現優美，使用順手，時間效率（ 複雜度O(n * n / log n)） ，空間效率 （複雜度O(n / log n)） 的。

如果需要一個可以不停地生成素數（而不會出現內存不夠）的寫法，就把上面的isPrime里依賴的primes換成naturals（所有自然數）就好了。 那樣就是常數空間複雜度了。

如果真的要速度最快的，那麼當然是用各種篩法，常用的是線性篩法寫起來也很簡單，據說也有亞線性的篩法。不過速度更快的都要吃更多內存了。

當然並行地做素數判定這種方法未在以上討論範圍之內。

PS：本來覺得回答這個問題挺影響比格的。。。然而大家居然拿出來的都是這麼丑的代碼，實在是手癢。。。要是大大們覺得這個回答比格裝得還行請點贊，謝謝。

WordBasic

Function Prim(n)
Dim a(n)
Dim i, j, x, p
For i = 2 To n
a(i) = 1
Next
a(0) = 0
a(1) = 0
For i = 2 To n
If a(i) = 1 Then
j = i + i
While j &<= n a(j) = 0 j = j + i Wend End If Next FileNew .NewTemplate = 0, .Template = "NORMAL" Insert "All prime numbers smaller than" Insert Str$(n) InsertPara For i = 2 To n If a(i) = 1 Then Insert Str$(i) Insert "," End If Next End Function Sub MAIN Begin Dialog UserDialog 214, 100 Text 25, 10, 125, 13, "Largest Number:" TextBox 24, 32, 160, 18, .SNum OKButton 75, 66, 88, 21 End Dialog Dim sinput As UserDialog Dim n Dialog sinput n = Int(Val(sinput.snum)) "MsgBox Str$(n) If n &> 0 Then
a = Prim(n)
Else
MsgBox("Wrong Input!")
End If
End Sub

運行環境和運行結果

推薦個文章吧：

求質數演算法的N種境界(N &> 10)

好了，現在更新個並行計算的版本，利用MPI。有沒有mapreduce也來PK一下，當然不許欺負我機器爛！！

#include &
#include & #include &
#include &

#define BLOCK_LOW(id,p,n) ((id)*(n)/(p))
#define BLOCK_HIGH(id,p,n) (BLOCK_LOW((id)+1,p,n)-1)

int main(int argc, char **argv)
{
int count; //local prime count
double elapse_time; //parallel execution time
int first; //index of first multiple
int global_count; //global prime count
int high_value; //highest value on this proc
int i;
int id; //process ID number
int index; //index of current prime
int low_value; //lowest value on this proc
char *marked; //portion of 2,...,"n"
int n;
int p; //number of processed
int proc0_size; //size of the 0"s sbuarray
int prime; //current prime
int size; //elements in "marked"

MPI_Init(argc, argv);

MPI_Barrier(MPI_COMM_WORLD);
elapse_time = - MPI_Wtime();
MPI_Comm_rank(MPI_COMM_WORLD, id);
MPI_Comm_size(MPI_COMM_WORLD, p);

if(argc != 2)
{
if(!id)
{
printf("Command line: %s &
", argv[0]);
}
MPI_Finalize();
exit(1);
}
n = atoi(argv[1]);

low_value = 2 + BLOCK_LOW(id, p, n-1);
high_value = 2 + BLOCK_HIGH(id, p, n-1);
size = high_value-low_value+1;

proc0_size = (n-1)/p;
if((2+proc0_size) &< (int)sqrt((double)n)) { if(!id) { printf("Too many processes "); } MPI_Finalize(); exit(1); } marked = (char*) malloc(size); if(marked == NULL) { printf("Cannot allocate enough memory "); MPI_Finalize(); exit(1); } for(i=0; i& low_value)
{
first = prime * prime - low_value;
}
else
{
if(!(low_value%prime))
{
first = 0;
}
else
{
first = prime-(low_value%prime);
}
}
for(i=first; i&

現在看看效果：

  • mpiexec -n 1 eratosthenes_parallel 100 Total elapsed time: 0.000015

  • mpiexec -n 2 eratosthenes_parallel 100 Total elapsed time: 0.000044

  • mpiexec -n 4 eratosthenes_parallel 100 Total elapsed time: 0.000061

  • mpiexec -n 8 eratosthenes_parallel 100 Total elapsed time: 0.000102

啥？核數越多速度越低？計算量太小了，與網路延遲相比可以忽略不計了，所以核數多了，網路延遲高了，自然變慢了。

咱來看看大點的數（其實也不算大）

  • mpiexec -n 1 eratosthenes_parallel 10000000 Total elapsed time: 0.169026

  • mpiexec -n 2 eratosthenes_parallel 10000000 Total elapsed time: 0.088593

  • mpiexec -n 4 eratosthenes_parallel 10000000 Total elapsed time: 0.044794

  • mpiexec -n 8 eratosthenes_parallel 10000000 Total elapsed time: 0.022485

這回正常點了吧。

所以嘛，對於一百以內的質數問題（以及很多類似問題），不要來知乎了，直接算出來，然後打表多好呀，又快又省事。

pascal：
var
a:array [1..100] of integer;
i,j,k:integer;
begin
for i:=1 to 100 do a[i]:=i;
a[1]:=0;i:=2;
while i&<=100 do begin k:=i; while k&<=100 do begin k:=k+i; a[k]:=0; end; {————上面將所有a[i]的倍數清0} i:=i+1; while a[i]=0 do i:=i+1; {————查找接下來的第一個非0數} end; for i:=1 to 100 do if a[i]&<&>0 then write(a[i]," ");
end.
-----------------------------------------------------------------------------------
8086：

data segment

D1 DW 200 DUP(0) ;定義數組

data ends

code segment
main proc far
assume cs:code,ds:data

start:
push ds
xor ax,ax
push ax

MOV AX,DATA
MOV DS,AX

MOV DX,1
MOV SI,OFFSET D1

NEXT:
INC DX
;ADD SI,2
CMP DX,100 ;100以內的數
JAE EXIT

MOV AX,DX
SHR AX,1 ;/2
DEC AX
MOV CX,AX
MOV BL,1

LOOP1:
INC BL ;2,3，....
MOV AX,DX
DIV BL
CMP AH,0
JE NEXT ;餘數為0，非素數

LOOP LOOP1
MOV [SI],DX ;保存素數
ADD SI,2
JMP NEXT

EXIT:
RET

main endp
code ends
end start

我也來個Python版本：

&>&>&> f = lambda x: [1 for v in xrange(1, int(math.sqrt(x)) + 1) if x % v == 0]
&>&>&> print [x for x in xrange(1, 100) if len(f(x)) == 1]

MATLAB大法好！

primes(100)

只有一行，多簡潔，結果：

ans =

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

怎麼能少了SQL 腳本？

--準備原材料
CREATE TABLE primes
(
number INT
)

DECLARE @i INT

SET @i = 2 --1不是質數，我們捨棄它
WHILE @i &< 100 BEGIN INSERT INTO primes VALUES (@i) SET @i+=1 END ---下面的查詢返回100以內的質數 SELECT A.* FROM primes A WHERE NOT EXISTS (SELECT number FROM primes B WHERE B.number &< A.number AND A.number % B.number = 0)

--你也可以這樣
--列印出100以內的質數
DECLARE @len INT
DECLARE @i INT
DECLARE @j INT
DECLARE @bl BIT

SET @len = 100
SET @i = 2
SET @j = 2

IF EXISTS (SELECT Object_id (N"TEMPDB..##temp1"))
BEGIN
DROP TABLE ##temp1

SELECT NULL AS "質數"
INTO ##temp1
END

--
WHILE @i &< @len BEGIN SET @bl = 0 WHILE @j &< @i BEGIN IF @i % @j = 0 BEGIN SET @bl = 1 BREAK; END SET @j+=1 END IF @bl = 0 BEGIN INSERT INTO ##temp1 VALUES (@I) END SET @j = 2 SET @i += 1 END DELETE ##temp1 WHERE 質數 IS NULL SELECT * FROM ##temp1

吃我一記大Racket啦.

#lang racket
(filter (lambda (x)
(letrec [(delim (integer-sqrt x))
(loop (lambda (iter)
(cond [(&> iter delim) true]
[(zero? (remainder x iter)) false]
[else (loop (add1 iter))])))]
(loop 2)))
(range 2 100))

人家只是想寫個作業，你們搞出來這麼多不能用的答案，題主要報警了！

推薦閱讀：

※如何設計（規劃）一款遊戲戰鬥系統的狀態機？
※易語言精通之後是不是能跟C++這些主流的編程語言一樣強大？
※Windows 平台下除了 Visual Studio，還有什麼軟體能編譯 C、C++ 文件？
※不想寫工作中的代碼，怎麼辦？

TAG:編程 |