#include <stdio.h> #include <math.h> int main() { int n,i; scanf("%d",&n); for( i=2;i<=n;i++) { if(n%i==0) break;//最普通的O(N) } if(i>=n&&n!=1) printf("YES"); else printf("NO"); return 0;}
下面的时间差不多是根号n
int cmp(int n) {int i; if(n==1) return 0;//特判1 for(i=2;i<sqrt(n);i++) {if(n%i==0) break; } if(i>sqrt(n)) return 1; return 0; }
