素数筛选算法的一种改进

摘要

本文对传统的素数筛选算法的缺点进行了分析和改进.并在埃拉托斯特尼筛法(sieve of Eratosthenes)的基础之上,设计了一种基于已知素数来寻找未知素数的区间筛法.区间筛法突破了由计算机内存分配造成的数量级限制,大幅提升了寻找素数的范围,并通过优化筛选过程提升了算法运行速度.实验结果表明,经过改进的区间筛法在筛选范围上远大于传统筛法,并且具有较好的时间复杂度.