时间戳

首页 > 解决方案 > 埃拉托色尼素数

c - 埃拉托色尼素数

问题描述

我创建了一个搜索素数的程序。在输入的数字小于 52 之前它可以正常工作，当它更大时输出会打印出一些空白 (0) 数字，我不知道为什么。其他数字也有空白输出。

我的代码是：

#include <stdio.h> //Prime numbers
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <unistd.h>

int c[100], n, a[50], d, e, b = 1;

void sort() {
    for (int i = 1; i < n; i++) {
        if (c[i] > 1) {
            a[b] = c[i];
            printf("%d %d %d\n", a[1], b, i);
            b++;
            e = 2;
            d = 0;
            while (d <= n) {
                d = c[i] * e;
                c[d - 1] = 0;
                e++;
            }
        }
    }
}

int main() {
    printf("Enter number as an limit:\n");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        c[i] = i + 1;
    }
    sort();
    printf("Prime numbers between 1 and %d are:\n", n);
    for (int i = 1; i < b; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

这是输出25：

Enter number as an limit:
25
2 1 1
2 2 2
2 3 4
2 4 6
2 5 10
2 6 12
2 7 16
2 8 18
2 9 22
Prime numbers between 1 and 25 are:
2 3 5 7 11 13 17 19 23

但对于83是：

Enter number as an limit:
83
2 1 1
2 2 2
2 3 4
2 4 6
2 5 10
2 6 12
2 7 16
2 8 18
2 9 22
2 10 28
2 11 30
2 12 36
2 13 40
2 14 42
2 15 46
2 16 52
0 17 58
0 18 60
0 19 66
0 20 70
0 21 72
0 22 78
0 23 82
Prime numbers between 1 and 83 are:
0 3 5 7 11 0 17 19 23 29 31 37 0 43 47 53 0 61 67 71 73 79 83

空白点总是出现在第 17 个素数之后。并且总是空白数字是相同的。你能帮我看看有什么问题吗？

标签： c

解决方案

c多次运行的循环设置条目c[i]太远：您应该在比较d 之前n计算下一个：

        for (d = c[i] * 2; d <= n; d += c[i]) {
            c[d - 1] = 0;
        }

事实上，您可以开始，d = c[i] * c[i]因为在外循环的先前迭代中已经看到了所有较低的倍数。

另请注意，将其存储i + 1到中会令人困惑：使用一组用于质数和复合c[i]的布尔值，代码会更简单。10

这是修改后的版本：

#include <stdio.h>

int main() {
    unsigned char c[101];
    int a[50];
    int n, b = 0;

    printf("Enter number as a limit:\n");
    if (scanf("%d", &n) != 1 || n < 0 || n > 100) {
        printf("invalid input\n");
        return 1;
    }
    for (int i = 0; i < n; i++) {
        c[i] = 1;
    }
    for (int i = 2; i < n; i++) {
        if (c[i] != 0) {
            a[b] = i;
            //printf("%d %d %d\n", a[0], b, i);
            b++;
            for (int d = i * i; d <= n; d += i) {
                c[d] = 0;
            }
        }
    }
    printf("Prime numbers between 1 and %d are:\n", n);
    for (int i = 0; i < b; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

输出：

chqrlie$ ./sieve4780
Enter number as a limit:
25
Prime numbers between 1 and 25 are:
2 3 5 7 11 13 17 19 23
chqrlie$ ./sieve4780
Enter number as a limit:
83
Prime numbers between 1 and 83 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79

推荐阅读