Primes Sequence Algorithm
The Prime Sequence Algorithm is an algorithmic technique used to generate a sequence of prime numbers. Prime numbers are natural numbers greater than 1 that have only two factors, 1 and the number itself. The algorithm is based on the principle of iterating through a range of numbers, starting from 2, and identifying the prime numbers by eliminating the multiples of each prime number found. One of the most famous prime number generation algorithms is the Sieve of Eratosthenes, which efficiently constructs a list of prime numbers up to a given limit.
The algorithm starts by creating a list of numbers from 2 to the desired upper limit. It then iteratively selects the smallest unmarked number in the list as a prime number, and removes all of its multiples from the list. This process is repeated until all the numbers in the list have been either marked as prime or removed as a multiple of a previously identified prime number. The remaining unmarked numbers in the list are the prime numbers within the specified range. The Prime Sequence Algorithm has several optimizations and variations, including the Sieve of Sundaram and Sieve of Atkin, which further improve the efficiency of prime number generation. These algorithms are widely used in number theory, computer science, and cryptography, as prime numbers play a crucial role in various applications, including encryption and secure communication protocols.
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace Algorithms.Sequences
{
/// <summary>
/// <para>
/// Sequence of prime numbers.
/// </para>
/// <para>
/// Wikipedia: https://wikipedia.org/wiki/Prime_number.
/// </para>
/// <para>
/// OEIS: https://oeis.org/A000040.
/// </para>
/// </summary>
public class PrimesSequence : ISequence
{
/// <summary>
/// Gets sequence of prime numbers.
/// </summary>
public IEnumerable<BigInteger> Sequence
{
get
{
yield return 2;
var primes = new List<BigInteger>
{
2,
};
var n = new BigInteger(3);
while (true)
{
if (primes.All(p => n % p != 0))
{
yield return n;
primes.Add(n);
}
n += 2;
}
}
}
}
}
