浅谈素数筛优化及其C++程序实现

倪 航, 刘 万能, 朱 小龙
江汉大学光电化学材料与器件教育部重点实验室

摘要

简单介绍了素数筛的三种方法：枚举法，埃氏筛法，欧拉筛法。通过C++程序实现，并作比较可知，优化后的枚举法仍然极为耗时，埃氏筛法大大缩减了用时，而欧拉筛法则进一步实现了明显的优化。本文对初学者有一定帮助。

关键词

素数筛；埃氏筛；欧拉筛

参考

[1]周利荣，胡天磊.Demytko素数构造算法优化及应用研究[J].电脑编程技巧与维护，2018（6）：54-59.

[2]马麟浚，黎百恬，王顺庆，秦建民，张开道.埃氏筛法的缺陷和理想最终筛法[J].今日科苑，2013（13）：108-114.

[3]叶煜，周洪林，任华.素数筛选法的改进及C语言实现[J].计算机与数字工程，2013（6）：899-900+964.

[4]张国钦，宋伟，马俊兴.素数筛选法的实现及优化[J].河南教育学院学报：自然科学版，2017（1）：39-41.