c - 从数组中计算素数的最短方法是什么？由于时间限制，所有正常的素性测试都没有通过测试用例

Question

下面给出的代码通过了两个测试用例，埃拉托斯特尼筛通过了 1 个测试用例。怎么解决这个问题。

我已经尝试过米勒·拉宾和筛埃拉托斯特尼素性测试。由于时间限制，没有人能够通过所有测试用例。有没有比这些更快的方法？下面的代码通过了 5 个测试用例中的两个。时间复杂度能再短一点吗？

#include<stdio.h>
#include<math.h>
int isPrime(int n) 
{
    int i;
    int x=(int)(sqrt(n));
    if(n==2)
    return 1;
    else if(n%2==0)
    return 0;
    else
    {
        for(i=3;i<=x;i+=2)
        {
            if(n%i==0)
            {
                return 0;
            }
        }
    }
    return 1;

}
int counting(int *a,int n)
{
    int i,c=0;
    for(i=0;i<n;i++)
    {
        if(isPrime(a[i]))
        c++;
    }
    return c;
}
void main()
{
    int cases,n,a[100000],i,j,count;
    scanf("%d",&cases);
    for(i=0;i<cases;i++)
    {
        scanf("%d",&n);
        for(j=0;j<n;j++)
        scanf("%d",&a[j]);
        count=counting(a,n);

        printf("%d\n",count);
    }
}

Answer 1

也许你应该尝试这个算法，我从这个 site 得到的。似乎更省时:

    #include <stdio.h>
    int main()
    {
        int n, i, flag = 0;
        printf("Enter a positive integer: ");
        scanf("%d", &n);
        for(i = 2; i <= n/2; ++i)
        {
            // condition for nonprime number
            if(n%i == 0)
            {
                flag = 1;
                break;
            }
        }
        if (n == 1) 
        {
          printf("1 is neither a prime nor a composite number.");
        }
        else 
        {
            if (flag == 0)
              printf("%d is a prime number.", n);
            else
              printf("%d is not a prime number.", n);
        }

        return 0;
    }