]]>
一个数Q如果只?和它本n两个因数Q这L数叫做质敎ͼ又称素数?/p>
在上??a target=_blank>素数法大全Q及CE序实现优化详解 (一) 试除?/a>》中我们已经探讨了求解素数的一cȝ法，q且试除法从最初的低效版本优化的高效的V2。那么，q有没有其它更佳法呢？q就是下面三藏要和大家探讨的内容
合数qo{选法
法描述Q我们知道，素数N不能?~(N-1)间的M数整除；反过来看Q只要能?~(N-1)间的M数整除的NQ都不是素数。所以我们可以采用一个简单的排除法：是对N以内的所有数Q只要逐个去除gؓ2~(N-1)的倍数的数Q剩下的是素数?/p>
C语言实现
// 合数qo{选法 Ver1
// 参数Qn 求解n以内(包括n)的素?br>// q回|n以内素数个数
int CompositeNumFilterV1(int n)
{
int i, j;
// 素数数量l计
int count = 0;
// 分配素数标记I间Q结合后文思考ؓ?1
char* flag = (char*)malloc( n+1 );
// 初始化素数标?
for (i=2; i<=n; i++)
{
// Z?(p+i)要写成flag[i]呢？可读性更佛_
flag[i] = 1;
}
// 写程序要注意排版和留I，方便阅读Q也可减出错几?br> // ?~(N-1)为因子过滤合?
for (i=2; i < n; i++)
{
for (j=2; i*j <= n; j++)
{
// i*j是由i,j两整数相乘而得Q显然不是素?br> flag[i*j] = 0;
}
}
// l计素数个数
for (i=2; i<=n; i++)
{
// 其实if(flag)其同样作用了，但这么写是有留言?
// 请参阅《C语言E序设计常见错误剖析及解决之道》一?
if (1 == flag[i]) count++;
}
// 因输Ӟ且和法核心相关不大Q故?br>
// 释放内存Q别忘了传说中的内存泄漏
free(flag);
return count;
}
在上文给出的main函数中以不同参数调用CompositeNumFilterV1函数Q得到执行结果如下：
[100000]以内素数个数Q?592, 计算用时Q?5毫秒
[1000000]以内素数个数Q?8498, 计算用时Q?25毫秒
[5000000]以内素数个数Q?48513, 计算用时Q?578毫秒
[10000000]以内素数个数Q?64579, 计算用时Q?281毫秒
注：因程序是非独占性运行的Q所以时间不是完全精的Q但基本能反映实?/p>
昄Q比上文中的试除法要快，而且谁都可以看到上例是一个未l优化的_陋版本Q好多地Ҏ三藏故意采用比较低效做法Qؓ了与后文的优化版比较Q凸显优化之重要Q也Z初学者记住别采用cM低效做法Q下面我们开始优化之?/p>
优化分析
上面CompositeNumFilterV1函数存在的问题有Q?/p>
- 在外层@环，需要一直执行到n-1吗？不要Q因为n/2~n-1间的数显然不能整出n
- 在内层@环中重复使用i*j昄是低效的Q考虑到计机中加减运速度比乘除快Q可以考虑变乘法ؓ加法
- 在@环修改flagq程中，其实有很多数会被重复计算若干ơ，比如6=2*3=3*2Q会被重复置0Q类似操作很多，所以我们得设法避免或减flag重复|?
据上q分析，我们可将E序优化如下Q?/p>
// 合数qo{选法 Ver2
// 参数Qn 求解n以内(包括n)的素?br>// q回|n以内素数个数
int CompositeNumFilterV2(int n)
{
int i, j;
// 素数数量l计
int count = 0;
// 分配素数标记I间Q明?1原因了吧Q因为浪费了一个flag[0]
char* flag = (char*)malloc( n+1 );
// 初始化素数标讎ͼ要高效点?br> flag[2] = 1;
// 注意是i<n不是上例中的i<=n了，理由自?
for (i=3; i<n; i++)
{
flag[i++] = 1;
// 偶数自然不是素数Q直接置0好了
flag[i] = 0;
}
// n为奇?
if (n%2 != 0)
{
flag[n] = 1;
}
// ?开始filterQ因?的倍数早在初始化时代就q掉?br> // 到n/2止的理由q要说吗
for (i=3; i <= n/2; i++)
{
// i是合敎ͼh着吧，因ؓ您的工作早有您的质因子代劳了
if (0 == flag[i]) continue;
// 从i?倍开始过滤，变乘法ؓ加法
for (j=i+i; j <= n; j+=i)
{
flag[j] = 0;
}
}
// l计素数个数
for (i=2; i<=n; i++)
{
if (flag[i]) count++;
}
// 因输Ӟ且和法核心相关不大Q故?br>
// 释放内存Q别忘了传说中的内存泄漏
free(flag);
return count;
}
再来调用CompositeNumFilterV2得到执行l果Q?/p>
[100000]以内素数个数Q?592, 计算用时Qn太小Q时间精度不?br>[1000000]以内素数个数Q?8498, 计算用时Q?1毫秒
[5000000]以内素数个数Q?48513, 计算用时Q?53毫秒
[10000000]以内素数个数Q?64579, 计算用时Q?062毫秒
[100000000]以内素数个数Q?761455, 计算用时Q?2973毫秒
哇哇Q比昨天的试除发快了好多倍，可见法的威力，值得好好学习Q别说学法没用咯?/p>
上例着那个计算一亿以内的素数只要U?3U，应该不错了Q今天是否可以休息了呢？NoQ我们要q求极限Q?/p>
int CompositeNumFilterV3(int n)
{
int i, j;
// 素数数量l计
int count = 0;
// 分配素数标记I间Q明?1原因了吧Q因为浪费了一个flag[0]
char* flag = (char*)malloc( n+1 );
// q嘛用的Q请仔细研究下文
int mpLen = 2*3*5*7*11*13;
char magicPattern[mpLen];
// 奇怪的代码QwhyQ思考无法代劻I惻I
for (i=0; i<mpLen; i++)
{
magicPattern[i++] = 1;
magicPattern[i++] = 0;
magicPattern[i++] = 0;
magicPattern[i++] = 0;
magicPattern[i++] = 1;
magicPattern[i] = 0;
}
for (i=4; i<=mpLen; i+=5)
magicPattern[i] = 0;
for (i=6; i<=mpLen; i+=7)
magicPattern[i] = 0;
for (i=10; i<=mpLen; i+=11)
magicPattern[i] = 0;
for (i=12; i<=mpLen; i+=13)
magicPattern[i] = 0;
// 新的初始化方??,3,5,7,11,13的倍数全干?br> // 而且采用memcpy以mpLen长的magicPattern来批量处?
int remainder = n%mpLen;
char* p = flag+1;
char* pstop = p+n-remainder;
while (p < pstop)
{
memcpy(p, magicPattern, mpLen);
p += mpLen;
}
if (remainder > 0)
{
memcpy(p, magicPattern, remainder);
}
flag[2] = 1;
flag[3] = 1;
flag[5] = 1;
flag[7] = 1;
flag[11] = 1;
flag[13] = 1;
// ?7开始filterQ因?,3,5,7,11,13的倍数早被kill?
// 到n/13止的Q哈哈，了好多?br> int stop = n/13;
for (i=17; i <= stop; i++)
{
// i是合敎ͼh着吧，因ؓ您的工作早有您的质因子代劳了
if (0 == flag[i]) continue;
// 从i?7倍开始过?br> int step = i*2;
for (j=i*17; j <= n; j+=step)
{
flag[j] = 0;
}
}
// l计素数个数
for (i=2; i<=n; i++)
{
if (flag[i]) count++;
}
// 因输Ӟ且和法核心相关不大Q故?br>
// 释放内存Q别忘了传说中的内存泄漏
free(flag);
return count;
}
再看CompositeNumFilterV3执行l果Q?/p>
[1000000]以内素数个数Q?8498, 计算用时Q?5毫秒
[5000000]以内素数个数Q?48513, 计算用时Q?03毫秒
[10000000]以内素数个数Q?64579, 计算用时Q?15毫秒
[100000000]以内素数个数Q?761455, 计算用时Q?421毫秒
再次优化后速度提升了又一倍左叻I三藏不禁有点满了，睡觉也！
]]>
密码Qxcc123456
如果大家有c++QopenGLQ密码学{等计算机方面的好资料，也可以发l我Q我的邮是 percyph@163.com
大家也可以回帖要资料Q如果有的话我会W一旉发上?br>怿来我q儿的朋友都是有素质的，请不要删除和Ud邮箱里的文gQ谢谢！
目前已经上传的资料有Q（以后会陆l更斎ͼ
VC~程助手Q小软gVC++ assistantQ能使编E更方便Q?br> C++Primer3Q电子书Q?br> glut函数说明Q电子书Q?br> C++技能百l（l典法Q?rar
ROAM地Ş法演示E序.rar
OpenGL 参考手?br> c&c++深层探烦
C++必知必会
VC6.0~程实例_解
高质量C++~程指南&~程新手真言&MFCcd详解
WindowsE序设计
MFCcd详解.chm
C++ 数据l构W三?nbsp;
C++ 数据l构W三?nbsp;
E序员面试宝?amp;E序员超U开发宝?nbsp;
c++和OpenGL函数手册
Essential C++中文?pdf
Effective C++(电子?
C++~程思想Q电子书Q?
3.11号上传（kuafoo发的Q?/span>
Windows环境?2位汇~语a.chm(2.78M)
深入出MFC
深入出MFCW二?br>
另外最q几个月写的数据l构的程序也传上MQ有兴趣的朋友可以看看！
里面包括Q?/p>
U性表——静态链?009.7.30
U性表——链表的内部cd?008.8
U性表——链表的友元cd?008.8
U性表——双向链?009.8.11
U性表——顺序表2009.8.3
U性表——友元模板类2009.8
U瑟夫问题——四U解?009.8.11Q数l，链表Q@环链表等Q?br>队列——队列的序表示循环队列2009.8.11
队列——链队列2009.8.11
栈——汉诺塔2009.8.6
栈——进制{?009.8.6
栈——括号匹?009.8.6
栈——模杉K?009.8.3
栈——模杉K序栈2009.7
栈——顺序栈2009.8.6
栈——算术表辑ּ求?009.7.13
栈——行~辑2009.8.6
二叉树——二叉树的常见操?009.9.3
2010.3.9 更新
树的应用—仿DOS文g夹管理程?/p>
200位大C?rar
200位大数加?rar
q连看单机程序MFC
]]>
在C中定义一个结构体cd要用typedef:
typedef struct Student
{
int a;
}Stu;
于是在声明变量的时候就可：Stu stu1;
如果没有typedef必ȝstruct Student stu1;来声?br>q里的Stu实际上就是struct Student的别名?br>另外q里也可以不写StudentQ于是也不能struct Student stu1;了）
typedef struct
{
int a;
}Stu;
但在c++里很单，直接
struct Student
{
int a;
};
于是定义了l构体类型StudentQ声明变量时直接Student stu2Q?br>===========================================
2其次Q?/span>
在c++中如果用typedef的话Q又会造成区别Q?br> struct Student
{
int a;
}stu1;//stu1是一个变?nbsp;
typedef struct Student2
{
int a;
}stu2;//stu2是一个结构体cd
使用时可以直接访问stu1.a
但是stu2则必d stu2 s2;
然后 s2.a=10;
===========================================
3 掌握上面两条可以了Q不q最后我们探讨个没多大关pȝ问题
如果在cE序中我们写Q?br> typedef struct
{
int num;
int age;
}aaa,bbb,ccc;
q算什么呢Q?br>我个察编译器QVC6Q的理解Q这相当?br> typedef struct
{
int num;
int age;
}aaaQ?br> typedef aaa bbb;
typedef aaa ccc;
也就是说aaa,bbb,ccc三者都是结构体cd。声明变量时用Q何一个都可以,在c++中也是如此。但是你要注意的是这个在c++中如果写掉了typedef关键字，那么aaaQbbbQccc是截然不同的三个对象?img src ="http://www.shnenglu.com/percyph/aggbug/75742.html" width = "1" height = "1" />
]]>
int glutVideoResizeGet(GLenum param);
q回glut视频大小调整的信?
参数:
param:
GLUT_VIDEO_RESIZE_POSSIBLE:如果底层支持视频大小调整,则返回非0?否则q回0.如果q回0,则其他视频大调整函数的调用不起作?
GLUT_VIDEO_RESIZE_IN_USE
GLUT_VIDEO_RESIZE_X_DELTA
GLUT_VIDEO_RESIZE_Y_DELTA
GLUT_VIDEO_RESIZE_WIDTH_DELTA
GLUT_VIDEO_RESIZE_HEIGHT_DELTA
GLUT_VIDEO_RESIZE_X
GLUT_VIDEO_RESIZE_Y
GLUT_VIDEO_RESIZE_WIDTH
GLUT_VIDEO_RESIZE_HEIGHT
后面几个帔R值在|上没有搜到解释.
//*******************************************************************************************
void glutSetupVideoResizing(void);
void glutStopVideoResizing(void);
void glutVideoResize(int x, int y, int width, int height);
void glutVideoPan(int x, int y, int width, int height);
我把glut的头文g中的所有函数都整理了一?只可?video resize sub-API中的几个函数|上都没有具体的介绍,本菜鸟也无能为力,q好q些函数都不是常用的,我想一般用不着.除了和视频有关的API,前面几个帖子的内容已l基本把glut的所有函数都q了一?本专题也q是完成了,以后如果扑ֈ相关资料,会把q里的补?也希望达够指点一?
]]>
//*******************************************************************************************
void glutGameModeString(const char *string);
通过一个字W串对game mode(游戏模式,也即全屏模式)q行讄,卛_屏幕q行讄.
参数:
string:一个指向字W串的指?字符串的内容x对屏q的讄.字符串的格式如下所C?
"W*H"
"W*H:Bpp"
"W*H@Rr"
"W*H:Bpp@Rr"
"@Rr"
":Bpp"
"Bpp:@Rr"
(?W:屏幕宽度,以像素单?H:屏幕高度,以像素ؓ单位;Bpp:每个像素的内存大?位数);Rr:屏幕的刷新率.)
例子:
1.如果我们只关心屏q大?800*600)而不兛_每个像素的内存占用和h频率,可以写成:
glutGameModeString("800*600");
2.如果只想把每个像素的内存占用讄?2?可以写成:
glutGameModeString(":32");
3.如果只想把刷新率讄?5赫兹,可以写成:
glutGameModeString("@75");
4.如果前三U情况都考虑,可以写成:
glutGameModeString("800*600:32@75");
其他情况按照上面l出的字W串格式写出卛_.
?
1.q个函数只是对硬件的h,如果讄不合?则将被忽?
2.q个函数q不q回错误?如果要获得错误信?则要用glutGameModeGet()函数.
//*******************************************************************************************
int glutEnterGameMode(void);
q入相应的game mode,卌glutGameModeString()的设|生?
//*******************************************************************************************
void glutLeaveGameMode(void);
dglutGameModeString()讄的game mode.
//*******************************************************************************************
int glutGameModeGet(GLenum mode);
设|的模式是否有效
参数:
mode:
GLUT_GAME_MODE_ACTIVE:如果E序q行在game mode,则返回非0?如果q行在窗口模?则返?.
GLUT_GAME_MODE_POSSIBLE:判断glutAameModeString()的设|是否有?如果有效则返回非0?否则q回0.但是glut手册中有一个警?即ɘq个讄是有效的,也不能保证屏q设|可以一定成功生?
GLUT_GAME_MODE_WIDTH:q回屏幕的宽?
GLUT_GAME_MODE_HEIGHT:q回屏幕的高?
GLUT_GAME_MODE_PIXEL_DEPTH:q回当前模式下每个像素所占用的内存空?位数).
GLUT_GAME_MODE_REFRESH_RATE:q回实际的刷新率(单位赫兹).
GLUT_GAME_MODE_DISPLAY_CHANGED:正如前面所?不能保证屏幕昄模式一定根据设|发生改?q个帔R可以用来试是否真的q入了game mode(先前是窗口模式下的情况下),如果先前已经是game mode,则可以用来测试设|是否发生改?q回?DC入了game mode或设|已l发生改?否则q回0.
]]>