素数筛

#include <cstdio> int su[1000000+11] = {1,1}; //1为非素数，0为素数 int main() { for (int i = 2 ; i <= 1000000 ; i++) { if (su[i] == 1) continue; for (int j = i * 2 ; j <= 1000000 ; j += i) su[j] = 1; } int n; while (~scanf ("%d",&n)) { if (su[n] == 0) printf ("素数\n"); else printf ("非素数\n"); } return 0; }