求某个范围内的所有素数（内含埃氏筛法

Description  求小于n的所有素数，按照每行10个显示出来。  Input  输入整数n(n<10000）。  Output  每行10个依次输出n以内的所有素数。如果一行有10个素数，每个素数后面都有一个空格，包括每行最后一个素数。  Sample Input  100  Sample Output  2 3 5 7 11 13 17 19 23 29  31 37 41 43 47 53 59 61 67 71 

73 79 83 89 97

挨个判断

 时间复杂度为O(n√n)

#include<stdio.h> int main() { int i, k, n, t = 0; scanf("%d", &n); for (i = 2; i <= n; i++) { for (k = 2; k<i; k++) if (i%k == 0) break; if (i == k) { printf("%d ", i); t+=1; if (t % 10 == 0) printf("\n"); } } return 0; }

=======================================================================================

埃氏筛法求素数：

1.把2到n范围内的整数写下来

2.其中2是最小的素数。故将表中所有的2的倍数划去

3.表中剩下的最小的数字就是3。再划去3的倍数

4.以此类推，如果表中剩余的最小的数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数

埃氏筛法：时间复杂度是O(nloglogn)。

#include<cstdio> #include<algorithm> //#include<windows.h> #define max 5000 using namespace std; int main() { int pri[max], n; int i, j; int count; //计数 换行 printf("please enter a number:\n"); scanf("%d", &n); for (i = 2;i <= n;i++) //假设每个数都是素数 pri[i] = 1; for (j = 3;j <= n;j++) //首先筛除2的倍数 { if (j % 2 == 0) pri[j] = 0; } for (i = 3;i < sqrt(n);i = i + 2) //判断素数，若不是 令pri[i]=0 { for (j = i*i;j <= n;j = j + 2) { if (pri[i] != 0 && (pri[j] != 0)) { if (j%i == 0) pri[j] = 0; } } } for (i = 2, count = 0;i <= n;i++) { if (pri[i]==1) { count++; if (count % 10 == 0) printf("\n"); printf("%d ", i); } } printf("\n"); //system("pause"); return 0; }

=============================================================

复制的：

#include <cstdio> using namespace std; const int maxn = 1000000 + 10; int prime[maxn]; //第i个素数 bool is_prime[maxn]; //is_prime[i]为true表示i是素数 //返回n以内的素数的个数 int sieve(int n) { int p = 0; for (int i = 0; i <= n; i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; i++){ if (is_prime[i]){ prime[p++] = i; for (int j = 2 * i; j <= n; j += i) is_prime[j] = false; } } return p; } int main() { int n; while (scanf("%d", &n) != EOF){ printf("%d\n", sieve(n)); } return 0; }