What's the Most Elegant Way to Generate Prime Numbers in C# or Java?

Pursuing elegance: best practices for prime number generation in C# or Java

Prime number generation has always been a topic that programmers have long explored. How to strike a balance between speed and code clarity has become the key to algorithm design. This article explores elegant ways to generate prime numbers in C# or Java.

Improved Sieve of Eratosthenes

The sieve of Eratosthenes is one of the common methods for finding prime numbers. By iteratively removing multiples of each prime number, we can filter out all non-prime numbers. The following code is an improvement on the standard sieve algorithm:

<code class="language-c#">public static List<int> GeneratePrimes(int limit)
{
    if (limit < 2) return new List<int>();

    var primes = new bool[limit + 1];

    for (int i = 2; i * i <= limit; i++)
    {
        if (!primes[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                primes[j] = true;
            }
        }
    }

    var result = new List<int>();
    for (int i = 2; i <= limit; i++)
    {
        if (!primes[i])
        {
            result.Add(i);
        }
    }
    return result;
}</code>

Prime number generation based on LINQ

Another approach is to take advantage of LINQ's lazy evaluation feature. This code returns an infinite sequence of prime numbers:

<code class="language-c#">public static IEnumerable<int> GeneratePrimesLINQ()
{
    yield return 2;
    yield return 3;

    var primes = new HashSet<int> { 2, 3 };

    for (int i = 5; ; i += 2)
    {
        if (!primes.Any(p => i % p == 0))
        {
            primes.Add(i);
            yield return i;
        }
    }
}</code>

Method selection

Which method to choose depends on the specific application scenario. The modified Sieve of Eratosthenes is efficient at finding a fixed number of prime numbers, while the LINQ-based method provides a lazy infinite sequence suitable for incremental processing. Ultimately, the most elegant solution is one that meets a specific need clearly and efficiently.

The above is the detailed content of What's the Most Elegant Way to Generate Prime Numbers in C# or Java?. For more information, please follow other related articles on the PHP Chinese website!