Sieve Method

精典例题NOI 1.5 -31:开关灯

假设有N盏灯(N为不大于5000的正整数)，从1到N按顺序依次编号，初始时全部处于开启状态；有M个人(M为不大于N的正整数)也从1到M依次编号。

第一个人（1号）将灯全部关闭，第二个人（2号）将编号为2的倍数的灯打开，第三个人（3号）将编号为3的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和3号一样，将凡是自己编号倍数的灯做相反处理。

请问：当第M个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用逗号间隔。

输入

输入正整数N和M，以单个空格隔开。

输出

顺次输出关闭的灯的编号，其间用逗号间隔。

样例输入

10 10

样例输出

1,4,9

例题解析

#include <iostream>
#include <cmath>
//#define MAXN 5000

int main(){

    freopen("t.in", "r", stdin);
    int n, m, i, k=0;
    scanf("%d %d",&n, &m);
    bool number[n+1];
    for( i=1; i<=n ; i++) number[i]=false;//第一个人将灯全部赋为true;

    for( i=2; i<=n ; i+=2) number[i]=true; //第二个人将编号为2的倍数的灯全部打开

    int j;
    for(j=3; j<=m; j++){  
        for( i=j; i<=n; i+=j ){
            if( number[i]==true ) number[i]=false;
            else number[i]=true;
        }//让第i人倍数的灯做相反操作；
    }    

    for( i=1; i<=n; i++){
        if(number[i]==false){
            k++;
            if(k==1) printf("%d",i);
            else printf(",%d",i);
        }
    }
     return 0;
}

精典例题 《从问题到程序》

http://www.is.pku.edu.cn/~qzy/books/ptop/v2004/ 第六章数据对象的顺序组合

数据对象的顺序组合：数组

6.2.2筛法求素数

例:求素数的一种著名方法叫“筛法”，其基本方法是取一个从2开始的整数序列，通 过不断划掉序列中非素数的整数(合数)，逐步确定顺序的一个个素数。具体做法是:

1. 令n等于2，它是素数;

2. 划掉序列中n的所有倍数(2*n，3*n等等);

3. 找到n之后下一个未划掉的元素，它是素数，令n等于它，回到步骤2。

现在要求写一个程序，输出从2到某个数之间的所有素数。

#include <stdio.h>
#include <math.h>

enum { NUM = 200 };
int an[NUM+1];//这里定义的数组包含 NUM+1 个元素，因为考察范围直至 NUM。
//求平方根时加 1 是为了防止 浮点误差带来麻烦。例如，无法保证 sqrt(9)是 3，
//它也可能等于 2.9999999......，把这个 数转换为整数就会变成 2。加 1 后的数再求平方根就没问题了

int main () {

    int i, j, upb = sqrt(NUM+1);
 an[0] = an[1] = 0; /* 建立起初始向量 */
  找出num的平方根可界定需要排查的最大数据范围
    for (i = 2; i <= NUM; ++i) an[i] = 1;
    for (i = 2; i <= upb; ++i)

        if (an[i] == 1)

        for (j = i*2; j <= NUM; j += i)

             an[j] = 0;

    for (i = 2, j = 0; i <= NUM; ++i)
        if (an[i] != 0)
            printf ("%d%c", i, ((++j)%10 == 0 ? '\n' : ' '));
//10个数为一行；
    putchar('\n');

return 0;
}