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

Question

下面给出的代码通过了两个测试用例，eratosthenes的筛子通过了一个测试用例。这个问题怎么解决呢？

我已经尝试过miller rabin和sieve eratosthenes素性检验。由于时间限制，没有人通过所有的测试用例。还有比这些更快的方法吗？下面的代码通过了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;
    }