埃拉托色尼筛法和他的素数

Question

这是我的代码：

#include <stdio.h>

int main() {
    int number;
    int prime[200000] = { 0 };
    int i = 0;
    int j = 0;
    int number1[200] = { 0 };
    int t = 0;
    int count = 0;
    int newprime2[200][200];
    int counter[200] = { 0 };
    int square;
    int count1;

    while ((scanf("%d", &number) ==  1 ) && (number != 0)) {
        number1[count] = number;
        ++count;
    }
    count1 = count;
    for (count = 0; count < count1; ++count) {
        if (number1[count] < 0) {
            fprintf(stderr, "Error: Invalid input!\n"); 
            return 100;
            break;
        }
        for (i = 0; i < number1[count]; i++) {
            prime[i] = i;
        }
        for (i = 2; (i < (number1[count])); i++) {
            if (prime[i] != 0) {       
                for (j = 2; (j < (number1[count])); j++) {
                    {
                        prime[j*prime[i]] = 0;
                        if (prime[i] * j > (number1[count]))
                            break;
                    }
                }
            }
        }
        t = 0;
        for (i = 2; i < number1[count]; ++i) {
            if ((prime[i] != 0) && (number1[count] % prime[i] == 0)) {
                newprime2[count][t] = prime[i];
                ++t; 
            }
        }
        printf("\n");
        printf("%i is made out of these primes\n", number1[count]);
        counter[count] = 0;
        square = 0;

        for (i = 0; i < t; ++i) {
            while (number1[count] % newprime2[count][i] == 0) {
                number1[count] = number1[count] / newprime2[count][i];
                square++;
            }
            counter[count]++;
            /* if number isn't made out of any of these primes*/
            if (!newprime2[count][i]) {   /*Why is this not working?*/
                printf("%i ", number1[count]);
            }  
            if (counter[count] == 1) {
                printf("%i^%d ", newprime2[count][i], square);
            }  else {
                printf("* %i^%d ", newprime2[count][i], square);
            }
            square = 0;
        }
    }
    printf("\n");

    return 0;
}

比如我的输入是：1 11 120 8 0

输出如下所示：

1 is made out of these primes
11 is made out of these primes
120 is made out of these primes
2^3 * 3^1 * 5^1 
8 is made out of these primes
2^3

但输出应该如下所示：

1 is made out of these primes
1
11 is made out of these primes
11
...

语句(!newprime2[count][i])是说这个数组是空的吧？那么为什么它不起作用？为什么我什至不能使用 gcc -pedantic -Wall -Werror -std=c99 -O3 ？有人可以帮助我吗？

Answer 1

行

if (!newprime2[count][i])

如果在 for 循环之前 t==0 则不会达到

，如果输入是素数或整数，情况就是如此。只需检查 t 并在其为零时结束。

或者早点检查它是否是统一的或者它已经在 prime 中。

我无法用 gcc -pedantic -Wall -Werror -std=c99 -O3 重复你的问题。

Answer 2

查看您的这部分代码：

    t = 0;
    for (i = 2; i < number1[count]; ++i){
        if ((prime[i]!=0) && (number1[count] % prime[i]==0)){
            newprime2[count][t] = prime[i];
            ++t;
        }

如果 number1[count] 是 1，那么 for 循环的主体 将不会执行 ，因此 t 将保持其价值 (0)。因此下一个循环的主体

        for (i=0; i < t; ++i){

也不会执行。

对于数字 11，此循环的主体将执行，但它将 无任何操作 作为 if 语句将 总是 false。因此它会导致 相同的问题 - t 将保持其值 0 并产生相同的结果。

Answer 3

您的算法既过于复杂又过于近似：

您不需要执行筛选来分解数字，您可以只枚举除数，复合除数将有一个非零余数，因为它们的质因数已经被删除。
筛子不完整：您转到 200000 如果 int 类型是 32 位（46341 就足够了），那将是过大的杀伤力，如果 int是64位。

这是一个简化版本：

#include <stdio.h>

int main(void) {
    int number, i, p, n, factors, count;
    int numbers[200];

    for (count = 0; count < 200 && scanf("%d", &number) ==  1; count++) {
        if (number == 0)
            break;
        if (number < 0) {
            fprintf(stderr, "Error: Invalid input!\n");
            return 100;
        }
        numbers[count] = number;
    }
    for (i = 0; i < count; i++) {
        number = numbers[i];
        printf("%d is made out of these primes\n", number);
        factors = 0;
        for (p = 2; p * p <= number; p += 1 + (p & 1)) {
            if (number % p == 0) {
                n = 0;
                factors++;
                do {
                    number /= p;
                    n++;
                } while (number % p == 0);
                if (n == 1)
                    printf("%d ", p);
                else
                    printf("%d^%d ", p, n);
            }
        }
        if (factors == 0 || number != 1)
            printf("%d", number);
        printf("\n");
    }
    return 0;
}

埃拉托色尼筛法和他的素数

Sieve of Eratosthenes and his primes

c

primes

sieve-of-eratosthenes