An Efficient Algorithm to Find All Primes in A Given Interval

Abstract

In this paper, we propose a deterministic algorithm for primality testing and primes search in a giveninteger interval. The algorithm use a new primality test method, which replace modulo operator with elementaryarithmetic operations, hence a better efficiency than divisibility test. The algorithm is working; it generates a primebase by an expansion process and is appropriate for a fast search for small primes (a dozen of digits). We propose afiltering method to overcome memory constraints, and use the algorithm to expand much more the prime base andfind medium size primes (dozens of digits).