【杭电oj】2138 - How many prime numbers（判断素数新方法）
【杭电oj】2138 - How many prime numbers（判断素数新方法）
How many prime numbers
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14851 Accepted Submission(s): 5143
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 4Sample Output
2Author
wangye
Source
HDU 2007-11 Programming Contest_WarmUp
判断素数的题要说已经做过很多了，以前都是用打表的方法，这道题因为要求输入的数在int范围内，打表不能做。
第一种方法很普通，就是判断2到跟号n是否有n的约数，很好理解。
代码如下：
#include <stdio.h>
#include <math.h>
bool prime(int t)
{
if (t==2 || t==3 || t==5)
return true;
if (t<2)
return false;
for (int i=2;i<=sqrt((double)t);i++)
{
if (!(t%i))
return false;
}
return true;
}
int main()
{
int ans;
int n;
int t;
while (~scanf ("%d",&n))
{
ans=0;
while (n--)
{
scanf ("%d",&t);
if (prime(t))
ans++;
}
printf ("%d\n",ans);
}
return 0;
}下面的方法是在网上找到，个人觉得更好，如果理解了将会比上面的省时间，我为了方便自己理解，加了详细的注释，贴出学习学习：
#include <stdio.h>
#include <math.h>
int base[8]={4,2,4,2,4,6,2,6};
// 分析：
//7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67
// 4 2 4 2 4 6 2 6 4 2 4 2 4 6 2 6
// 从7开始算加法，依次加42424626，可以得到所有质数
int prime(int t)
{
if (t<2) //0,1为非素数
return 0;
if (t==2 || t==3 || t==5) //对小于7的素数单独判断
return 1;
if (!(t%2 && t%3 && t%5)) //被2、3、5的倍数不为素数
return 0;
//注意上述判断的先后顺序
int n=7; //从7开始加
for (;n<=sqrt(double(t));)
{
for (int i=0;i<8;i++) //从7开始列出素数判断
{
if (t%n==0)
return 0;
n+=base[i];
}
if (t%n==0) //之前少判断一次，所以单独判断
return 0;
}
return 1; //如果上述判断都通过，则为素数
}
int main()
{
int ans;
int n;
int t;
while (~scanf ("%d",&n))
{
ans=0;
while (n--)
{
scanf ("%d",&t);
if (prime(t))
ans++;
}
printf ("%d\n",ans);
}
return 0;
}腾讯云开发者
