HDU ACM Steps：How many prime numbers

问题描述

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

输入

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

输出

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

输入样例

3
2 3 4

输出样例

2

思路

1.判断每个数是否为素数并计数即可
2.比较简单的判断素数的方法：
如果N是合数，则一定存在大于1小于N的整数a和b，使得$N=a \times b$N=a×b。
如果a和b均大于N，则有：$N＝d1×d2>\sqrt{N}\times\sqrt{N}＝N$N＝d1×d2>N​×N​＝N。
所以a和b中必有一个小于$\sqrt{N}$N​。
因此只需要遍历$\sqrt{N}$N​之前的数即可，也就是满足$i \times i<=N$i×i<=N。
3.有兴趣可以去看一下大佬的写的各种素数算法：素数算法

代码

#include<stdio.h>

int n,m;

int is_prime(int m)
{
	long long i;//注意，这里不能定义为int，因为i*i的结果会储存在i，可能会溢出
	for (i=2; i*i<=m; ++i)
	 {
		if (m%i==0) return 0;
	}
	return 1;
}
int main()
{
	
	while(~scanf("%d",&n))
	{
		int ans=0;
		while(n--)
		{
			scanf("%d",&m);
			if(is_prime(m)) ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
 }