确定Prime或复合数

Question

我正在编写一个程序来确定给定的数字是素数还是复合数.我的代码是我到目前为止的代码.我认为使用WHILE LOOP不会像FOR LOOP那样有效,但我可能错了.

#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我没有得到回报,因为它没有除以3.我可以加入这个WHILE LOOP来补偿或者我会更容易使用FOR LOOP吗？

我在想,如果我使用FOR LOOP,我可以这样开始.

    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);