1978/12/01 by David Gries, Jayadev Misra · 1 citation
Mathematics · Computer Science · Engineering · #Analytic Number Theory Research #Algorithms and Data Compression #graph theory and CDMA systems #Mathematics #Prime number #Prime (order theory) #Algorithm #Time complexity #Prime factor #Discrete mathematics #Multiplication (music) #Arithmetic #Integer (computer science) #Factorization #Combinatorics #Computer science
paper · pdf · doi:10.1145/359657.359660
openalex publication_date 1978/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
A new algorithm is presented for finding all primes between 2 and n . The algorithm executes in time proportional to n (assuming that multiplication of integers not larger than n can be performed in unit time). The method has the same arithmetic complexity as the algorithm presented by Mairson [6]; however, our version is perhaps simpler and more elegant. It is also easily extended to find the prime factorization of all integers between 2 and n in time proportional to n .