How many prime numbers（素数）

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

Author

wangye

Source

HDU 2007-11 Programming Contest_WarmUp

 1 #include<stdio.h>
 2 #include<math.h>
 3   int prime(int x)
 4     {  int i;
 5         if(x<=2)   return 1;
 6         for(i=2;i<=sqrt(x*1.0);i++)   //i*i<=x  是会超时的，因为i*i每次都要计算
 7           {
 8               if(x%i==0)  
 9                 {
10                     return 0;
11                     break;
12                 }
13           }
14         return 1;
15     }
16   int main()
17     {
18         int n;
19         int i;
20         int sum;
21         int a;
22         while(scanf("%d",&n)!=EOF)
23           {
24                  sum=0;
25                for(i=0;i<n;i++)
26                 {
27                     scanf("%d",&a);
28                       if(prime(a))
29                         sum++;
30                 }      
31               printf("%d
",sum);     
32           }
33         return 0;
34         
35     }