c - 确定质数或合数

Question

我正在编写一个程序来确定给定数字是素数还是合数。我下面的代码是我到目前为止所拥有的。我认为使用 WHILE 循环不如 FOR 循环有效，但我可能错了。

#include <stdio.h>

int main(int argc, const char* argv[]) {
    int num, i;

    printf("Enter a number you want to check:");
    scanf("%d", &num);
    if (num == 1) {
        printf("%d is neither prime nor composite", num);
    }
    i = 2;
    while (i <= num - 1) {
        if (num % i == 0) {
            printf("%d is composite\n\n", num);
            break;
        }
    }
}

该程序适用于大多数偶数，但当我到达 9 时，我没有得到返回，因为它不是除以三。我可以添加到这个 WHILE 循环中来补偿还是我会更容易使用 FOR 循环？

我在想，如果我使用 FOR 循环，我可以像这样开始它。

    for (i = 2, i <= num, i++) {
        num % i == 0;
    }
    printf("%d is Composite", num);
}

Answer 1

你忘了在你的循环中增加索引

while (i <= num-1) {
    if (num%i==0) 
    {
        printf("%d is composite\n\n",num);
        return; // test is finished
    }
    i++;   // increase i by 1
}

printf("%d is prime number\n", num); // add this line to display the prime numbers also

编辑

我只是来看看你对 for 循环的使用的评论:

for (i = 2; i < num; i++)  // ① be careful of ; and , ② i<num not i<=num
{
    if(num % i == 0)      //  if your num is dividable ==> not prime
    {
        printf("%d is Composite", num);
        return 0;      // return from the main func
    }
}
printf("%d is prime number\n", num);   // no divisor = no return = prime number

编辑 2

现在让我们谈谈效率:要确定数字是否为质数，您可以迭代不到它的一半，如何？

如果 p 是数字并且 k 是它的除数那么:

p = k * n

if ( n > sqrt(p)  && k > sqrt(p))
==> n * k > p

对任何整数取任何一对约数，两个约数不能同时大于整数的平方根!

这就是为什么你可以像这样迭代:

while (i <= sqrt(num)) {
        if (num%i==0) 
        {
            printf("%d is composite\n\n",num);
            return; // test is finished
        }
        i++;   // increase i by 1
    }

因此对于您的 10000，您只需迭代 100 次!而不是你想的 5000 ;)

进一步

如果你的预算真的很紧，你可以只检查大于 2 的奇数 :D，我的意思是如果它不能被 2 整除，那么它永远不能被 4、6、8 整除...... . 跳过它们

示例:

if(num%2 == 0) // check for 2
{
    printf("%d is composite\n\n",num);
    return;
}
while (i <= sqrt(num))  // check only for odd # greater than 2
{
     if (num%i==0) 
     {
         printf("%d is composite\n",num);
         return; // test is finished
     }
     i+=2;   // increase i by 2
}
printf("%d is prime\n", num);