一个素数的问题,但是求的是素数的个数,怎么利用C语言的办法解决的

Problem Description
Give you a lot of positive integers, just to find out how many prime numbers there are.

Input
There are a lot of cases. In each case, there is an integer N representing the number of integers to find. Each integer won’t exceed 32-bit signed integer, and each of them won’t be less than 2.

Output
For each case, print the number of prime numbers you have found out.

Sample Input
3
2 3 4

Sample Output
2

2个回答

可以暴力解决,对于每一个数从2开始除道sqrt(N),检查是否为素数,复杂度O(n^1.5)

要么维护一个素数表,可以每次查询,复杂度O(n),素数表可以先找到最大的值再构造。

#include<stdio.h>
#include<math.h>

int main()
{
    int i, j, n;
    int tmp = 1;
    int count = 0;      //统计素数个数 
    int number[n];
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%d", &number[i]);
    }

    for(i=0; i<n; i++)
    {
        if(number[i] == 1)      //素数为大于1的自然数,为1时跳过 
            continue;
        for(j=2; j<=sqrt(number[i]); j++)
        {
            if(number[i]%j == 0)    //存在除了1和它本身以为的因数则不为素数 
            {
                tmp = 0;
                break;
            }   
        }
        if(tmp == 1)        //统计素数 
            count++;
    }

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

}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问