补充素数知识:
第一,对于一个自然数N,只要能被一个非1非自身的数整除,它就肯定不是素数,所以不
必再用其他的数去除。
第二,对于N来说,只需用小于N的素数去除就可以了。例如,如果N能被15整除,实际
上就能被3和5整除,如果N不能被3和5整除,那么N也决不会被15整除。
第三,对于N来说,不必用从2到N一1的所有素数去除,只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明:
如果N是合数,则一定存在大于1小于N的整数d1和d2,使得N=d1×d2。
如果d1和d2均大于√N,则有:N=d1×d2>√N×√N=N。
而这是不可能的,所以,d1和d2中必有一个小于或等于√N。
#include<stdio.h> #include<math.h> #include <queue> #include<algorithm> #include <iostream> #include <string.h> using namespace std; bool prime(int n) { int i; for(i=2;i<=sqrt(n*1.0);i++) { if(n%i==0)return 0; } return 1; } int main() { int t; while(~scanf("%d",&t)) { int ans=0; while(t--) { int temp; scanf("%d",&temp); if(prime(temp))ans++; } printf("%d\n",ans); } return 0; }