Sieve of Atkin

The sieve of Atkin is a fast, modern algorithm for determining all prime numbers up to a specified limit. It is an optimized version of the ancient Sieve of Eratosthenes: The Atkinsieb makes some preliminary work and then cross all multiples of prime squares. It was developed by A. O. L. Atkin and Daniel J. Bernstein.

Algorithm

  • All residues modulo 60 residues ( the remainder after division by 60 is considered ).
  • All numbers, and x and y are positive integers.
  • Below inverting an entry of Siebliste means that the mark ( prime or non- prime) is changed to the opposite.
  • If the entry contains a number with a remainder of 1, 13, 17, 29, 37, 41, 49, or 53, invert it for any solution of the equation: 4x ² y ² = n
  • If the entry contains a number with remainder 7, 19, 31, or 43, invert it for any solution of the equation: 3x ² y ² = n
  • If the entry contains a number with residue 11, 23, 47, or 59, invert it for any solution of the equation: 3x ² - y ² = n, where x > y.

Explanation

The algorithm ignores all numbers that are two, three or five divisible.

  • All numbers with modulo 60 residue 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, or 58, divided by two, and not primary.
  • All numbers with modulo 60 remainder 3, 9, 15, 21, 27, 33, 39, 45, 51, or 57 are divisible by three and not prime.
  • All numbers with modulo 60 remainder 5, 25, 35, or 55 are divisible by 5 and not prime. These residues are all ignored.
  • All numbers with modulo 60 remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo 4 remainder of 1 These figures are accurate then prime if the number of solutions for 4x ² y ² = n is odd and the number is square-free.
  • All numbers with modulo 60 remainder 7, 19, 31, or 43 have a modulo 6 remainder of 1 These figures are accurate then prime if the number of solutions for 3x ² y ² = n is odd and the number is square-free.
  • All numbers with modulo 60 residue 11, 23, 47, or 59 have a modulo 12 remainder of 11 These figures are accurate then prime if the number of solutions for 3x ² - y ² = n is odd and the number is square-free.
  • None of the potential prime numbers are divisible by 2, 3, or 5, so they can not be divisible by their squares. Therefore, the square of freedom is not checked at 2 ², 3 ² and 5 ².

Complexity

To complexity theory: The screen requires operations with only bits memory consumption.

The Sieve of Eratosthenes needed operations and bits.

Here is the Landau symbol and the number of examined numbers.

Square-free integer
728986
de