Primes
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
using System;
using System.Linq;
using System.Collections.Generic;
public enum Mode {
Time,
Value,
Count,
NextByValue,
NextByCount
}
public class Factor {
public uint Value { get; set; }
public uint Count { get; set; }
public Factor(uint value) {
Value = value;
Count = 1;
}
public void Increment() {
Count++;
}
public override string ToString() {
return $"{Value}{(Count > 1 ? $"^{Count}" : "")}";
}
}
public class Factors {
List<Factor> List { get; set; } = new List<Factor>();
public bool IsPrime { get { return List.Count == 1 && List.First().Count == 1; } }
public uint Value { get; set; }
public void Add(uint value) {
if(List.Any(f => f.Value == value)) {
List.Single(f => f.Value == value).Increment();
}
else {
List.Add(new Factor(value));
}
}
public static List<Factors> FactorizeRange(uint min, uint max) {
var facsList = new List<Factors>();
var primes = MainClass.GetPrimes(Mode.Value, max);
for(var i = min; i <= max; i++) {
facsList.Add(new Factors(i, primes));
}
return facsList;
}
public Factors(uint value, List<uint> primes = null) {
this.Value = value;
if(primes == null) {
primes = MainClass.GetPrimes(Mode.Value, (uint)Math.Sqrt(value));
}
else {
var max = (uint)Math.Sqrt(value);
primes = primes.TakeWhile(p => p <= max).ToList();
}
while(value > 1) {
uint factor = primes.FirstOrDefault(p => value % p == 0);
if(factor == 0) {
factor = value;
}
value /= factor;
Add(factor);
}
}
public override string ToString() {
return string.Join(" * ", List.Select(f => f.ToString()));
}
}
public class MainClass {
public static List<uint> GetPrimes(Mode mode, uint value)
{
var primes = new List<uint>();
DateTime start = DateTime.Now;
uint i = 0;
uint nextCount;
Func<bool> limit;
switch(mode)
{
case Mode.Time:
limit = () => (DateTime.Now - start).TotalSeconds < value;
break;
case Mode.Count:
limit = () => (uint)primes.Count < value;
break;
case Mode.NextByValue:
nextCount = (uint)GetPrimes(Mode.Value, value).Count + 1;
limit = () => (uint)primes.Count < nextCount;
break;
case Mode.NextByCount:
nextCount = (uint)GetPrimes(Mode.Count, value).Count + 1;
limit = () => (uint)primes.Count < nextCount;
break;
case Mode.Value:
default:
limit = () => i <= value;
break;
}
for(i = 2; limit(); i++) {
var max = Math.Sqrt(i);
if(!primes.TakeWhile(p => p <= max).Any(p => i % p == 0)) {
primes.Add(i);
}
}
return primes;
}
static List<uint> GetPrimesInRange(uint min, uint max) {
var primes = GetPrimes(Mode.Value, max);
return primes.SkipWhile(p => p < min).ToList();
}
static void EvalPrimesByCalcTime(uint value) {
List<uint> primes;
primes = GetPrimes(Mode.Time, value);
Console.WriteLine($"{value} seconds: {primes.Last()}");
Console.WriteLine($"...and count: {primes.Count}");
value = (uint)Math.Pow(primes.Last(),.5);
Console.WriteLine($"{value} = sqrt({primes.Last()})");
Console.WriteLine();
primes = GetPrimes(Mode.Value, value);
Console.WriteLine($"highest prime under {value}: {primes.Last()}");
Console.WriteLine($"...and count: {primes.Count}");
Console.WriteLine();
value = primes.Last();
primes = GetPrimes(Mode.Count, value);
Console.WriteLine($"{value}th prime = {primes.Last()}");
}
static void EvalHighestValueByPrimeFactors(uint count) {
var primes = GetPrimes(Mode.Count, count);
Console.WriteLine($"{primes.Count}th prime: {primes.Last()}");
primes = GetPrimes(Mode.NextByCount, count);
Console.WriteLine($"{primes.Count}th prime: {primes.Last()}");
primes = GetPrimes(Mode.Value, (uint)Math.Pow(primes.Last(), 2));
Console.WriteLine($"Max prime coverage: {primes.Last(p => p != primes.Last())}");
}
static void Main()
{
//var primes = GetPrimes(Mode.Value, (uint)Math.Pow(622,.5));
//Console.WriteLine($"lowest prime factor for numbers up to 622 ranges from 2 to {primes.Last()}");
//Factors.FactorizeRange(529, 622).ForEach(value => Console.WriteLine($"{value.Value} = {value}"));
//EvalHighestValueByPrimeFactors(100);
EvalPrimesByCalcTime(14);
}
}
Csharp
INFO