0

我已经成功地为 C 中的素数实现了 Eratosthenes 的筛子（我知道有更快的方法来寻找素数，这只是一个学习练习），但是我还没有找到一种令人满意的方法来过滤我返回的素数数组为零。为了说明，当运行我的程序时返回：

$ ./初筛

输入搜索限制 > 100

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

$

我需要一些过滤零的方法。我假设有一些算法比仅在打印出答案之前迭代返回数组并将非零元素复制到第二个数组更有效，但我自己无法找到或想出一个。顺便说一下，整数数组在堆上是 malloc 的。

这是代码。

编辑：粘贴的最终代码实现了 zero_filter() 方法。Edit2：完全忘记了筛子只需要搜索到 sqrt(n)... 在下面的代码中修复。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include "dbg.h"

void init_array(int sieve[], int size) {

    int i;

    for(i = 0; i < size; i++) {
        sieve[i] = i;
    }

    sieve[1] = 0;
}

int prime_filter(int sieve[], int size, int root) {

    int i, j;
    int zero_count = 2;

    for(i = 2; i < root; i++) {
        if(sieve[i] != 0) {
            for(j = 2 * i; j < size; j += i) {
                if(sieve[j] != 0) {
                    sieve[j] = 0;
                    zero_count++;
                }
            }
        }
    }

    return zero_count;
}

void zero_filter(int sieve[], int final_array[], int size) {

    int i;
    int j = 0;

    for(i = 0; i < size; i++) {
        if(sieve[i] != 0) {
            final_array[j] = sieve[i];
            j++;
        }
    }
}

void print_array(int final_array[], int size) {

    int i;

    for(i = 0; i < size; i++) {
        printf("%d ", final_array[i]);
    }
}

void destroy_arrays(int *sieve, int *final_array) {

    if(sieve) {
        free(sieve);
    }
    if(final_array){
        free(final_array);
    }
}

int main(int argc, char *argv[]) {

    check(argc == 1, "No input required");

    int size, root, rv;  // upper limit on search, return value

    printf("Input search limit > ");
    rv = scanf("%d", &size);
    check(rv != EOF, "Input error on scanf().");
    check(rv != 0, "Input error, expected integer");

    root = (int) sqrt(size) + 1;

    int *sieve, *final_array;
    int zero_count, new_size;

    sieve = malloc(sizeof(int) * size);
    check(sieve != NULL, "Memory allocation error");

    init_array(sieve, size);
    zero_count = prime_filter(sieve, size, root);

    new_size = size - zero_count;

    final_array = malloc(sizeof(int) * (new_size));
    check(final_array != NULL, "Memory allocation error");

    zero_filter(sieve, final_array, size);
    print_array(final_array, new_size);
    destroy_arrays(sieve, final_array);

    printf("\n");
    return 0;

error:
    return -1;
}
4

2 回答 2

4

我认为你需要像std::removeC++ 中的函数。它就地“删除”元素。看看：std::remove 如果你不熟悉 C++ 和模板，这里采用的代码：

int *remove(int *first, int *last, int val)
{
  int *result = first;
  while (first!=last) {
    if (!(*first == val)) {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
}

您可以使用以下代码调用它：

int array[n];
int *end = remove(array, array + n, 0);
size_t not_removed_size = end - array; // values in range [array[0], ... array[not_removed_size]) are non-zeros.
于 2013-08-06T21:09:55.747 回答
1

您可以将数组转换到位以压缩前面的所有非零条目。像这样的东西，它返回找到的非零元素的数量（在我的脑海中 - 没有完全测试，但应该说明这个想法 - 特别是size应该被验证为理智）：

int compact(int array[], int size)
{ int current = 0, nextpos = 0;

  while (current < size)
  { if (array[current])
    { int tmp = array[nextpos];         // or use a properly defined swap()
      array[nextpos] = array[current];  // but this will be just as fast...
      array[current] = tmp;
      ++nextpos;
    }
    ++current;
  }
  return nextpos;
}
于 2013-08-06T21:17:08.253 回答