题面
素数是一个自然数，它恰好有两个不同的自然数除数：1 和它本身。 例如，前四个质数是：2、3、5 和 7。
编写一个程序，读取 N 个整数的列表并打印该列表中素数的个数。
输入
第一行包含一个整数 N，即列表中元素的数量。
N 个数字在以下几行中给出。
1≤N≤10000
2≤列表中的元素≤108
输出
打印给定列表中素数的数量。
法一：常规循环 复杂度O(n)
法二：由sqrt(x)处断开，提高运行效率
法三：质数总是分布在6x+1或者6x+5
#include <iostream> #include <math.h> using namespace std; /* int judge(int x) { for(int i=2; i<=sqrt(x); i++) //从开方那里截断减少运行时间 if(x%i==0) return 0; return 1; } */ //优化 //质数的特点，质数总等于6x+1 int judge(int x) { if(x<=3) return x>1; if(x%6!=1&&x%6!=5) return 0; for(int i=5; i<=sqrt(x); i+=6) if(x%i==0||x%(i+2)==0) return 0; } int main(void) { int n, count=0; cin>>n; int*p=(int*)malloc(n*sizeof(int)); //动态数组实现 int*q=p; for(int i=0; i<n; i++){ cin>>*q; if(judge(*q++)) count++; } cout<<count; free(p); return 0; }TRANSLATE with