此篇為Pointers in C Programming A Modern Approach to Memory Management, Recursive Data Structures, Strings, and Arrays
這本書第六章筆記其之一。
要說這兩個主題,可以用篩法的程式來解釋。篩法是可以列出n個數內所有質數的一個方法,原理很簡單,從2開始,,只要被2整除的(也就是2的倍數)都不是質數,全部去掉。去掉2的倍數後,除2以外最小的值是3,再把數列中3的倍數全部去掉,接下來的做法以此類推。
如果不用到指標,陣列版的程式如下:
int compact0(int n, int array[n])
{
int m = 0;
for (int i = 0; i < n; i++) {
if (array[i] > 0)
array[m++] = array[i];
}
return m;
}
int eratosthenes(int n, int buf[n - 2])
{
// Init
for (int i = 2; i < n; i++) {
buf[i - 2] = i;
}
// Sieve
for (int i = 0; i*i < n - 2; i++) {
if (buf[i] == 0) continue;
int p = buf[i];
for (int j = p*p; j < n; j += p) {
buf[j - 2] = 0;
}
}
// Compact
return compact0(n - 2, buf);
}
我們的main裡面有一個buf陣列,傳進去compact0跟eratosthenes後不需return,函式結束後都會使陣列的內容改變,所以只要return陣列中最後一個質數的位置即可。
而這裡的eratosthenes函式的做法,並不是把非質數去掉,而是歸零,所以需要compact0函式把0給去掉,並把數字擠在一起。
指標板就是重點了,其程式碼如下:
int *sieve_candidates_(int *from, int *to, int p)
{
int *output = from;
for (int *input = from ; input < to; input++) {
if (*input % p != 0)
*output++ = *input;
}
return output;
}
int eratosthenes__(int n, int buf[n - 2])
{
// Init
for (int i = 2; i < n; i++) {
buf[i - 2] = i;
}
// Sieve
int *candidates = buf;
int *end = buf + n - 2;
while (candidates < end) {
int p = *candidates++; // Get prime and move it
end = sieve_candidates_(candidates, end, p);
}
return end - buf;
}
最需要注意的是以下程式碼:
for (int *input = from ; input < to; input++) {
if (*input % p != 0)
*output++ = *input;
}
這一段就是直接把陣列裡的數字取代掉,原始陣列如下圖
那是怎麼把2的倍數通通消掉的?(如下圖)
假設目前p==2,*input==5
,那麼目前的ouput在3這個位置上。*output++ = *input;
這句話,會讓ouput往前一格跑到4上面,接下來*input
的值會取代4。接下來的值都是以此類推。
至於回傳型態,可以參照下面程式碼:
void sieve_candidates__(int **from, int **to)
{
int p = *(*from)++;
int *output = *from;
for (int *input = *from ; input < *to; input++) {
if (*input % p != 0)
*output++ = *input;
}
*to = output;
}
int eratosthenes___(int n, int buf[n - 2])
{
// Init
for (int i = 2; i < n; i++) {
buf[i - 2] = i;
}
// Sieve
int *candidates = buf;
int *end = buf + n - 2;
while (candidates < end) {
sieve_candidates__(&candidates, &end);
}
return end - buf;
}
其實跟上面程式碼意思是一模一樣的,但可以發現根本就不用return,直接assign給一個指標就好,這算是把to宣告成雙重指標的好處吧。
完整程式碼如下:
#include <stdio.h>
int compact0(int n, int array[n])
{
int m = 0;
for (int i = 0; i < n; i++) {
if (array[i] > 0)
array[m++] = array[i];
}
return m;
}
int eratosthenes(int n, int buf[n - 2])
{
// Init
for (int i = 2; i < n; i++) {
buf[i - 2] = i;
}
// Sieve
for (int i = 0; i*i < n - 2; i++) {
if (buf[i] == 0) continue;
int p = buf[i];
for (int j = p*p; j < n; j += p) {
buf[j - 2] = 0;
}
}
// Compact
return compact0(n - 2, buf);
}
void sieve_candidates(int **from, int **to, int p)
{
int *output = *from;
for (int *input = *from ; input < *to; input++) {
if (*input % p != 0)
*output++ = *input;
}
*to = output;
}
int eratosthenes_(int n, int buf[n - 2])
{
// Init
for (int i = 2; i < n; i++) {
buf[i - 2] = i;
}
// Sieve
int *candidates = buf;
int *end = buf + n - 2;
while (candidates < end) {
int p = *candidates++; // Get prime and move it
sieve_candidates(&candidates, &end, p);
}
return end - buf;
}
int *sieve_candidates_(int *from, int *to, int p)
{
int *output = from;
for (int *input = from ; input < to; input++) {
if (*input % p != 0)
*output++ = *input;
}
return output;
}
int eratosthenes__(int n, int buf[n - 2])
{
// Init
for (int i = 2; i < n; i++) {
buf[i - 2] = i;
}
// Sieve
int *candidates = buf;
int *end = buf + n - 2;
while (candidates < end) {
int p = *candidates++; // Get prime and move it
end = sieve_candidates_(candidates, end, p);
}
return end - buf;
}
void sieve_candidates__(int **from, int **to)
{
int p = *(*from)++;
int *output = *from;
for (int *input = *from ; input < *to; input++) {
if (*input % p != 0)
*output++ = *input;
}
*to = output;
}
int eratosthenes___(int n, int buf[n - 2])
{
// Init
for (int i = 2; i < n; i++) {
buf[i - 2] = i;
}
// Sieve
int *candidates = buf;
int *end = buf + n - 2;
while (candidates < end) {
sieve_candidates__(&candidates, &end);
}
return end - buf;
}
void print_array(int *begin, int *end)
{
while (begin < end) {
printf("%d ", *begin++);
}
printf("\n");
}
int main(void)
{
int n = 100;
int buf[n - 2];
int m = eratosthenes(n, buf);
print_array(buf, buf + m);
m = eratosthenes_(n, buf);
print_array(buf, buf + m);
m = eratosthenes__(n, buf);
print_array(buf, buf + m);
m = eratosthenes___(n, buf);
print_array(buf, buf + m);
return 0;
}