程序设计基础[数据组织一]－筛法

1、课前思考题课前思考题程序输出是什么？程序输出是什么？整理课件你 做 对 了 吗 ？整理课件3整理课件4 筛法的算法思想与依据 筛法的程序实现特点 筛法与枚举思想的区别与联系 做标记、打标签的编程技术整理课件5整理课件6 0 1 2 3 4 5 6 7 99 100 0 0 1 0 1 0 1 1 整理课件7整理课件8nc 1整理课件9筛合数的过程整理课件10程序框图如下：程序框图如下： for ( c=2; c=100; c=c+1 ) for ( c=2; c=100; c=c+1 ) d = 2; ( 初始化 ) primec = 0; do while d = sqrt ( 100 )

2、primek = 1; k = k + d; while ( k = 100 ) k = k + d; yes primek = 0 no k = d; yes primec = 0 no cout c endl; d = d + 1; 整理课件11整理课件12整理课件13/ / 输出输出1 1100100中所有的质数中所有的质数/ / 使用使用“筛筛”法思想来实现法思想来实现#include / cout#include / sqrt()using namespace std;int main() int prime101 = 1, 1; / why 101 ? / 0,1肯定不是质数，先筛

3、去，相应位置的标记设为1.根据程序流程图编写源程序根据程序流程图编写源程序整理课件14int d = 2; / 从第一个质数2开始，筛除它们的倍数do int k = d;if (primek = 0) / / 只使用只使用没被筛掉没被筛掉的质数的质数k += d;/ k 是 d 的倍数while (k = 100) primek = 1; / / 被被“筛筛”掉了掉了k += d;/ k = k + d;d +; / 下一个 d while (d = sqrt(100);如何将如何将do.while, whiledo.while, while循环都改成循环都改成forfor循环？循环？整理课

4、件15for (int c=2; c=100; c+) if (primec = 0) cout c endl; /why not primec ? return 0;整理课件16如何如何将将do.while, whiledo.while, while循环都改成循环都改成forfor循环循环课后阅读整理课件17for (int d=2;int d=2; d=sqrt(100); d=d+1d=d+1)int k = d;if (primek = 0) for (k=k+d;k=k+d; k=100; k=k+d)primek = 1; / / 被被“筛筛”掉了掉了int last = sqrt

5、(100);int last = sqrt(100);for (int d=2;int d=2; d=last; d+d+)if (primed = 0) for (int k=dk=d* *2;2; k=100; k+=d)primek = 1; / IF / FOR简化代码改写代码改写整理课件18for (int d=2;int d=2; d=sqrt(100); d=d+1d=d+1)int k = d;if (primek = 0) for (k=k+d;k=k+d; k=100; k=k+d)primek = 1; / / 被被“筛筛”掉了掉了int last = sqrt(100);for (int d=2; d=last; d+)if (primed = 1 1) continuecontinue;for (int k=d*2; k=100; k+=d)primek = 1; / FOR简化代码改写代码改写整理课件19for (int d=2;int d=2; d=sqrt(100); d=d+1d=d+1)int k = d;if (primek = 0) for (k=k+d;k=k+d; k=100; k=k+d)primek = 1; / / 被被“筛筛”掉了掉了int last = sqrt(100);for (int d=2; d=last; d+)