# Prime engine: generation, primality, factorization

I've just written my first C# class, so I'm looking for some feedback before I go and write more code. The goal of the code is to provide a Singleton-like class to deal with common operations on the set of prime numbers that I will need to complete projecteuler.net problems.

I'm interested in feedback for all aspects of the implementation (short of the actual prime generation algorithms, the 6*i +/- 1 method was used solely for its simplicity).

I'm also interested in feedback about how the interfaces are split up. I split these up into slices of functionality in an attempt to allow future implementation changes. I am planning to use DI (e.g. SimpleInjector) to bind the singleton instance to each of the interfaces, but I'm seriously starting to doubt this pattern.

I'm less interested in feedback about the selections of methods, I just chose a relatively minimal subset of methods that I know that I will need at some point - more methods will probably be added as needed.

### Interfaces

public interface IPrimeGenerator
{
IEnumerable<long> PrimesUntilValue(long value);
IEnumerable<long> PrimesUntilCount(int count);
}

public interface IPrimeChecker
{
bool IsPrime(long value);
}

public interface IPrimeFactorizer
{
IEnumerable<long> PrimeFactors(long value);
IEnumerable<long> UniquePrimeFactors(long value);
}


### Implementation

public class PrimeEngine: IPrimeGenerator, IPrimeChecker, IPrimeFactorizer
{
private long _indexFactor;
private long _maxChecked;

public PrimeEngine()
{
_primeCollection = new Collection<long> {2, 3};
_indexFactor = 1;
_maxChecked = 3;
}

private void CheckNextPossiblePrimeDoublet()
{
var low = 6 * _indexFactor - 1;
var high = low + 2;

if (IsPrime(low))
{
}

if (IsPrime(high))
{
}

_indexFactor += 1;
_maxChecked = high;
}

private IEnumerable<long> GetPossibleSmallerPrimeFactors(long value)
{
FillPrimesUntilRoot(value);
return PrimesUntilRoot(value);
}

public bool IsPrime(long value)
{
var primePool = GetPossibleSmallerPrimeFactors(value);
return primePool.All(prime => value % prime != 0);
}

private void FillPrimesUntilValue(long value)
{
while (_maxChecked < value)
{
CheckNextPossiblePrimeDoublet();
}
}

private void FillPrimesUntilCount(int count)
{
while (_primeCollection.Count < count)
{
CheckNextPossiblePrimeDoublet();
}
}

private static long FloorOfRoot(long value)
{
return (long) Math.Floor(Math.Sqrt(value));
}

private void FillPrimesUntilRoot(long value)
{
FillPrimesUntilValue(FloorOfRoot(value));
}

public IEnumerable<long> PrimesUntilValue(long value)
{
FillPrimesUntilValue(value);
return _primeCollection.TakeWhile(prime => prime <= value);
}

public IEnumerable<long> PrimesUntilCount(int count)
{
FillPrimesUntilCount(count);
return _primeCollection.Take(count);
}

public IEnumerable<long> PrimesUntilRoot(long value)
{
return PrimesUntilValue(FloorOfRoot(value));
}

public IEnumerable<long> PrimeFactors(long value)
{
FillPrimesUntilRoot(value);
foreach (var prime in PrimesUntilRoot(value))
{
if (prime > value) break;

while (value % prime == 0)
{
yield return prime;
value /= prime;
}
}

if (value != 1)
{
yield return value;
}
}

public IEnumerable<long> UniquePrimeFactors(long value)
{
return PrimeFactors(value).Distinct();
}
}

• The two first interfaces are identical - a copy/paste mistake? Nov 26 '18 at 7:14
• In many applications of prime numbers a NextPrime(int value) method, returning the next higher prime can be useful. Hint: after 2 and 3, all prime numbers are of the form 6n ± 1. Nov 28 '18 at 15:01

This is excellent code for a beginner. It's neat, the methods are short, etc. However, there are a couple things I'm concerned with.

1) Your engine has a lot of state. It looks like this is mostly related to the generation of the next prime sequences, and any found primes are cached, so it shouldn't be too bad. However, you have to test that calling PrimesUntilValue followed by UniquePrimeFactors, for example, doesn't generate "duplicate" values or skip any.

2) Given that you are using an approximation for primes, your code is structured neatly. However, do note that actually generating the sequence might get a bit messier than this and don't expect to be able to swap it out neatly. Given that your class's state is solely used for generating the next prime and that all previously found values are cached, it shouldn't be an issue.

3) This code could lead to massive memory use in an application. Since you are already caching the values and all, you should consider making it a static class and making the cached collection a thread-safe hashmap. Then you have one instance of the prime engine and can do things like PrimeEngine.PrimesUntilRoot, etc. The hashmap would prevent duplicate primes from being entered into the collection.

I agree with @Hosch250 ... too much state in what really could be self-contained static methods. I am struggling to see why you would want any of the class-level variables.

I personally do not like the interfaces, mainly because you can define it only to 1 integer type (long or Int64). Why not Int32, UInt32, or even UInt64? Granted Int32 gets a free ride with the Int64 version.

For some functions, there is way too much bloat in terms of memory and time. If you want to check that a number is prime, why bother checking for its entire prime factors collection? Once you detect that a number is not prime, the IsPrime method should return immediately rather than clicking along to find out if there are other prime factors.

On a positive note, the code is written neatly and is easy to understand.

• How would I go about expanding the interfaces to accept variable types? Nov 26 '18 at 19:46
• @JaredGoguen That's just it - you can't, which is why I don't like the interfaces for this solution. Consider something like Math.Max. All the integral types have that method but it can't be tied to an interface because the interface declares one specific output type for a method. To put it another way, if you want an Int32 method to return an Int32, and a similarly named UInt64 method to return an UInt64, they can't be declared by an interface. Nov 28 '18 at 13:30
• Generics would work. IPrimeGenerator<T>
– user34073
Nov 30 '18 at 17:18