如果值是素数还是不更快,我该如何计算？

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