c - 如何不经除法反复查找数字是否为质数

Closed. This question needs to be more focused。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？更新问题，使其仅通过editing this post专注于一个问题。
                        
                        6个月前关闭。
                                                                                            
                
        
有人告诉我用C编写一个程序，以查找数字是否为质数并将其分解。我使用了重复除法，即我用从1到该数字的整数重复地除以该数字，如果余数为0且不超过2种情况（1和该数字），则该数字为质数，否则为质数。但是我的老师说，如果有很多输入，程序将花费很多时间来处理它，所以这是错误的。他说要创建一个新程序，但是如果不使用这种方法，我不明白如何检查数字是否为质数，所以请有人帮助我。

最佳答案

有人告诉我用C编写一个程序，以查找数字是否为质数并将其分解。


开始;忘记“是否是主要的”部分，而专注于“分解”。

分解数字首先尝试除以最小的质数，然后再除以最小的质数，然后...像这样：

    while(value % 2 == 0) {
        printf("2 ");
        value /= 2;
        if(value == 0) {
            goto done;
        }
    }
    while(value % 3 == 0) {
        printf("3 ");
        value /= 3;
        if(value == 0) {
            goto done;
        }
    }
    while(value % 5 == 0) {
        printf("5 ");
        value /= 5;
        if(value == 0) {
            goto done;
        }
    }

这会很烦人，所以让我们切换到质数数组，也许像这样：

    unsigned int array[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };

    for(index = 0; index < sizeof(array) / sizeof(array[0]); index++) {
        while(value % array[index] == 0) {
            printf("%u ", array[index]);
            value /= array[index];
            if(value == 0) {
                goto done;
            }
        }
    }
done: ;

当然，如果只有一个因素，那么您知道数字是质数，所以我们添加一下：

    unsigned int array[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
    int factorCount = 0;

    for(index = 0; index < sizeof(array) / sizeof(array[0]); index++) {
        while(value % array[index] == 0) {
            printf("%u ", array[index]);
            value /= array[index];
            factorCount++;
            if(value == 0) {
                goto done;
            }
        }
    }
done:
    if(factorCount == 1) {
        printf("Yep, that's a prime number\n");
    }

现在，该数组也将变得很烦人，尤其是对于大数（谁想手工写出一个大的素数数组？）。根据需要生成素数列表会更好。

为此，您需要“ Sieve_of_Eratosthenes”。有关说明，请参见：https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

关于c - 如何不经除法反复查找数字是否为质数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57438645/