Sign In

Communications of the ACM

ACM TechNews

New Take on an Ancient Method Improves Way to Find Prime Numbers

View as: Print Mobile App Share:
An illustration of the sieve of Eratoshthenes.

A mathematician at Germany's University of Gottingen has proposed an improvement to the sieve of Eratosthenes method for finding prime numbers.


Mathematician Harald Helfgott at Germany's University of Gottingen has proposed improving an ancient method for finding prime numbers by reducing the requirement of physical space in computer memory and shortening the execution time of programs designed to make that calculation.

Helfgott's proposal involves enhancing the sieve of Eratosthenes, which "grows in proportion to the size of the interval considered," notes Cornell University professor Jean Carlos Cortissoz Iriarte. "But if you look at what needs to be kept in memory for each step of the algorithm performed for large intervals [numbers], then the sieve stops being efficient."

Helfgott was inspired by combined approaches to the century-old circle method to modify the sieve to function with less physical memory space. In mathematical terms, this means it is now sufficient to have the cube root of "N" instead of a space "N."

"To calculate all primes up to a trillion, the modified version of the sieve requires a few million bits instead of a billion bits," Helfgott says.

He acknowledges this space reduction implies "minor" sacrifices in the algorithm's theoretical speed, but thinks in certain ranges this loss could be countered or surpassed by the possibility of chiefly or solely using the cache memory.

From Scientific American
View Full Article


Abstracts Copyright © 2016 Information Inc., Bethesda, Maryland, USA


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account