秘鲁数学家哈拉尔德·赫尔夫戈特在2013年解决了一个有271年历史的难题时获得了全球关注：即所谓的哥德巴赫弱猜想，根据该猜想，每个大于5的奇数都可以表示为三个素数之和——例如：3 + 3 + 5 = 11 和 19 + 13 + 3 = 35。
但是，38岁的赫尔夫戈特甚至追溯到更久远的时代，构思出了埃拉托斯特尼筛法的改进版本，这是一种公元前240年左右提出的、广受欢迎的素数查找方法。赫尔夫戈特提出的版本将减少计算机内存中物理空间的需求，从而减少为进行该计算而设计的程序的执行时间。
素数就像是“数学的原子”，只能被自身和数字1整除。昔兰尼的埃拉托斯特尼——一位希腊数学家、天文学家和地理学家，曾任亚历山大图书馆馆长，并因计算地球周长而闻名——也提出了一种实用的方法来识别它们：“筛法”，或过滤器。“像许多其他孩子一样，我10岁时在小学通过表格学到了这个，”赫尔夫戈特说，他目前是法国国家科学研究中心 (CNRS) 和哥廷根大学的研究员。
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保未来能够继续报道关于塑造我们当今世界的发现和思想的具有影响力的故事。
为了用这种筛法确定例如1到100之间的所有素数，必须按数字顺序写下数字列表，并按特定顺序开始划掉它们：首先，是2的倍数（除了2）；然后，是3的倍数，除了3；等等，从下一个未被划掉的数字开始。在此过程中幸存下来的数字将是素数。该方法可以被公式化为算法，计算机可以快速运行它。
赫尔夫戈特说，在为一本完整演示哥德巴赫弱猜想的书籍校对测试时，他开始思考——“也许花了太多时间”——关于埃拉托斯特尼筛法的问题。特别是关于它对空间或内存的要求。“今天的计算机非常快，也可以并行执行计算。但内存仍然是有限的，”赫尔夫戈特解释道。
康奈尔大学和洛斯安第斯大学的数学家让·卡洛斯·科尔蒂索斯·伊里亚特表示，为了了解一个算法有多好，必须考虑两个因素：给定输入（例如100）的每比特操作数，以及指令执行时要存储在内存中的比特数。“就每比特要执行的操作数而言，埃拉托斯特尼筛法相对有效。它与所考虑的区间大小成比例增长。但是，如果你看看对于大区间[数字]执行的算法的每个步骤需要保存在内存中的内容，那么筛法就不再有效了，”他说。
现在，受到对被称为圆法的百年解析技术的综合方法的启发，赫尔夫戈特得以改进埃拉托斯特尼筛法，使其在更少的物理内存空间中工作。用数学术语来说：不再需要空间N，现在只需要N的立方根就足够了。“为了计算高达万亿的所有素数，改进后的筛法需要几百万比特，而不是十亿比特，”赫尔夫戈特说。该提案的主要思想于7月在布宜诺斯艾利斯举行的第二十一届拉丁美洲代数研讨会和在巴黎举行的居住在欧洲的秘鲁科学家大会Sinapsis 2016上都进行了展示。
为了理解新筛法的优势，科尔蒂索斯提供了一个类比。“让我们假设你是一台计算机，并且你使用纸张来将数据存储在你的内存中。如果要计算1到1,000,000之间的素数，你需要200令纸（10,000张），而使用赫尔夫戈特提出的算法，你只需要五分之一令纸（约100张），”他说。
尽管减少空间需求通常意味着算法理论速度上的一些“微小”牺牲，但赫尔夫戈特认为，在某些范围内，这种不足可以通过主要或专门使用高速缓存内存来抵消或超过，高速缓存内存比主内存或RAM小但速度更快。“这取决于应用，”他说。
还有其他用于识别素数的筛法或算法。但赫尔夫戈特指出，埃拉托斯特尼筛法的不同之处在于，它还可以与其他数学运算（如因式分解）一起使用——因式分解是一种将任何数字分解为素数乘积的技术，并且是用于安全编码信息（例如用于进行电子银行转账或在线购物）的密码学方法的基础。“因式分解已成为当代文明的关键要素，”赫尔夫戈特说。埃拉托斯特尼永远不会想到这一点。