Custom Prime Sieve

I've come up with a prime number finder I call the "Progressive Sieve". I wouldn't doubt it if this has already been thought of. Anyway, here is the idea, an implementation in C#, and benchmarks:

Premise: A number is prime if it cannot be divided evenly by any prime number below its square root.

Implementation:

static List ProgressiveSieve(long bound)
    {
        List primes = new List() { 3 }; // start it with 3

        for (long i = 5; i  sqrt) // if j gets above the square root, then i must be prime
                {
                    primes.Add(i);
                    break;
                }

                if (i % j == 0) // i is evenly divisible, no need to continue checking
                {
                    break;
                }
            }
        }

        return (new List { 2 }).Concat(primes).ToList(); // Because of how I start it off, I'll just add 2 here
    }

Benchmarks:

• ProgressiveSieve(100,000): 10ms

• ProgressiveSieve(100,000,000): 75102ms

Is there any room for improvement? I feel like finding the square root takes a good bit of time. More importantly, though, is the code compiling down to the most efficient IL? Are there ways I could do the exact same thing faster with optimized C#?

This is my 2nd answer to your post. The first answer focused on comparing it to the Sieve of Eratosthenes. This answer will ignore Eratosthenes and just focus on your method in its own right: the coding style, what’s good, what’s bad, and areas for improvement.

First the Good News

Your use of braces is good and overall spacing is pleasant. The indentation is a bit off, though.

Your casing is good as well.

Areas of Improvement

The worst thing the method does is create 2 lists, which adversely affects memory and performance. There is a simple work around to this below. Fixing this can speed things up 3X.

While i and j are iteration variables, they really could have a more meaningful name. It’s not like i or j are indices into an array or list. I would rename i to number and I would possibly rename j to prime … that is if I keep the foreach (which I don’t).

You could also use var where the type is clearly obvious from a simple assignment statement. This is optional for many, since some violently oppose the var.

You also have no error checking, so someone could input a bound of -1.

Method Signature

I always insist on an access modifier. Anytime I see a method without one, I immediately assume a junior developer forget it, and I’m then prone to wonder what else they may have forgotten.

As mentioned in my 1st answer, you probably should stick with a domain of just int.

It seems obvious that the return type should be List but while internally the primes will be a List, the method could equally return an IList.

public static IList ProgressiveSieve(int bound)
{
    if (bound  int.MaxValue - 2)
    {
        throw new ArgumentException(nameof(bound));
    }

    var primes = new List() { 2, 3 }; // start it with 2 & 3

    for (var number = 5; number < bound; number += 2) // ignore even values, because they will never be prime except 2
    {
        var isprime = true;
        var sqrt = (int)Math.Sqrt(number);

        for (var j = 1; j < primes.Count && primes[j] <= sqrt; j++)
        {
            if (number % primes[j] == 0) // i is evenly divisible, no need to continue checking
            {
                isprime = false;
                break;
            }
        }

        if (isprime)
        {
            primes.Add(number);
        }
    }

    return primes;
}

Caution Near int.MaxValue

I check that bound is not too large at the top of the method. That why I’m not worried about number += 2 wrapping around to negatives.

One alternative would be to add an extra check in the for:

for (var number = 5; number 3; number += 2)

But this extra check will degrade performance somewhat.

Another alternative would be to have number be a long (but bound remains an int). This only helps at the very high end of int, and may impact performance as well.

The whole caution is to ask yourself what happens if someone puts in a MaxValue for a number type? What steps will you take to deal with that?

That said, Eratosthenes is still faster.

StackExchange Code Review Q#106770, answer score: 4