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开始除道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);
}