c - 确定用户输入的数字是否为质数的程序

Question

这个代码在 C 中会是什么样子？我确实尝试在 javascript 上执行此操作，但不知道如何循环它。确定用户输入的数字是否为质数的程序。该程序将继续询问数字，直到用户输入小于 2 的值。该程序必须使用模块来实现。例子 ：

Enter a number: 4
4 is not a prime number 
Enter a number: 5
5 is a prime number 
Enter a number: 0

---

int main()
{
   int n, i = 3, count, c;

   printf("Enter the number of prime numbers required\n");
   scanf("%d",&n);

   if ( n >= 1 )
   {
      printf("First %d prime numbers are :\n",n);
      printf("2\n");
   }

   for ( count = 2 ; count <= n ;  )
   {
      for ( c = 2 ; c <= i - 1 ; c++ )
      {
         if ( i%c == 0 )
            break;
      }
      if ( c == i )
      {
         printf("%d\n",i);
         count++;
      }
      i++;
   }

   return 0;
}

Answer 1

这是一般未优化的算法：

int n;
do
{
    printf("Enter the number: ");
    scanf("%d",&n);

    if (n >= 2) // check if number is prime, general algorithm
    {
        bool prime = true;
        for (int j=2; j<n; j++)
            if ( (n%j) == 0) // n is divided by j without modulus - is it not prime
            {
                prime = false;
                break;
            }

        if (prime)
            printf("prime\n");
        else
            printf("is not prime\n");
    }
} while (n >= 2);

这是更新版本，它使用了所有偶数都不是素数的事实，并且检查大于 N/2 的数字是没有意义的

int n;
do
{
    printf("Enter the number: ");
    scanf("%d",&n);

    if (n >= 2) // check if number is prime, general algorithm
    {
        bool prime = true; // for n=2 prime is true
        if (n > 2)
            prime = n & 1; // number at least odd

        if (prime)
        {
            // starts with 3
            for (int j=3; j<=(n>>1); j+=2)
                if ( (n%j) == 0) // n is divided by j without modulus - is it not prime
                {
                    prime = false;
                    break;
                }
        }

        if (prime)
            printf("prime\n");
        else
            printf("is not prime\n");
    }
} while (n >= 2);

Answer 2

实际上，检查直到 sqrt(n) 就足够了，这将使您的代码运行得更快。

您可以查看这篇文章以了解其他有用的方法。