c - 如何计算一个值是否更快？

Question

我的程序在我的编译器中运行良好，但在在线竞赛编译器中显示超过时间限制。
输入的第一行将包含一个数字 N = 测试用例的数量。接下来的 N 行将包含数字 n 作为测试用例，其中 0<=n<=1000000000
这是我的代码。

   #include<stdio.h>
   void main()
   {   
   long t,n,i;
   int f = 0;
   scanf("%lu",&t);
   while(t--)
   {
       scanf("%lu",&n);
       f=0;
       if(n==0 || n==1)
       {
           printf("NOT PRIME\n");
       }
       else 
       {
       for(i=2;i<=n/2;i++)
       {
           if(n%i == 0)
           {
               printf("NOT PRIME\n");
               f =1;
               break;
            }
       }
       if(f==0)
       {
           printf("PRIME\n"); 
       }
   }
   }
}

我怎样才能更快地执行这个程序。帮我。提前致谢。

Answer 1

您可以迭代到 n 的平方根而不是 n/2。也可以在while循环之前预先计算出1000000000平方根范围内的所有质因数。然后尝试将 n 除以小于或等于 sqrt(n) 的素数因子，以检查它是否为素数。

for 循环:

(i = 3; i <= sqrt(n); i += 2) // skip 2 because it's the only even prime