Skip to content

Instantly share code, notes, and snippets.

@arlm

arlm/.gitignore

Last active March 30, 2017 00:59
Show Gist options
  • Save arlm/6647474 to your computer and use it in GitHub Desktop.
Save arlm/6647474 to your computer and use it in GitHub Desktop.
Download ZIP
Prime numbers IEnumerable in C#
Raw
BruteForce.cs
using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
public partial class Primes
{
public static IEnumerable<int> BruteForcePrimes (int max)
{
if (max < 2) yield break;
yield return 2;
List<int> found = new List<int> ();
found.Add (3);
int candidate = 3;
while (candidate <= max) {
bool isPrime = true;
foreach (int prime in found) {
if (prime * prime > candidate) {
break;
}
if (candidate % prime == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
found.Add (candidate);
yield return candidate;
}
candidate += 2;
}
}
}
Raw
Clock.cs
using System;
using System.Diagnostics;
using System.Threading;
using System.Collections.Generic;
using System.Linq;
public class Clock {
interface IStopwatch {
bool IsRunning { get; }
TimeSpan Elapsed { get; }
void Start();
void Stop();
void Reset();
}
class TimeWatch : IStopwatch {
Stopwatch stopwatch = new Stopwatch();
public TimeSpan Elapsed {
get { return stopwatch.Elapsed; }
}
public bool IsRunning {
get { return stopwatch.IsRunning; }
}
public TimeWatch() {
if (!Stopwatch.IsHighResolution) throw new NotSupportedException("Your hardware doesn't support high resolution counter");
//prevent the JIT Compiler from optimizing Fkt calls away
long seed = Environment.TickCount;
//use the second Core/Processor for the test
Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(2);
//prevent "Normal" Processes from interrupting Threads
Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
//prevent "Normal" Threads from interrupting this thread
Thread.CurrentThread.Priority = ThreadPriority.Highest;
}
public void Start() {
stopwatch.Start();
}
public void Stop() {
stopwatch.Stop();
}
public void Reset() {
stopwatch.Reset();
}
}
class CpuWatch : IStopwatch {
TimeSpan startTime;
TimeSpan endTime;
bool isRunning;
public TimeSpan Elapsed {
get {
if (IsRunning) throw new NotImplementedException("Getting elapsed span while watch is running is not implemented");
return endTime - startTime;
}
}
public bool IsRunning {
get { return isRunning; }
}
public void Start() {
startTime = Process.GetCurrentProcess().TotalProcessorTime;
isRunning = true;
}
public void Stop() {
endTime = Process.GetCurrentProcess().TotalProcessorTime;
isRunning = false;
}
public void Reset() {
startTime = TimeSpan.Zero;
endTime = TimeSpan.Zero;
}
}
public static void BenchmarkTime(Action action, int iterations = 10000) {
Benchmark<TimeWatch>(action, iterations);
}
static void Benchmark<T>(Action action, int iterations) where T : IStopwatch, new() {
//clean Garbage
GC.Collect();
//wait for the finalizer queue to empty
GC.WaitForPendingFinalizers();
//clean Garbage
GC.Collect();
//warm up
action();
var stopwatch = new T();
var timings = new double[5];
for (int i = 0; i < timings.Length; i++) {
stopwatch.Reset();
stopwatch.Start();
for (int j = 0; j < iterations; j++) action();
stopwatch.Stop();
timings[i] = stopwatch.Elapsed.TotalMilliseconds;
Console.Out.WriteLine(timings[i]);
}
Console.Out.WriteLine("normalized mean: {0}", timings.NormalizedMean().ToString());
}
public static void BenchmarkCpu(Action action, int iterations = 10000) {
Benchmark<CpuWatch>(action, iterations);
}
}
public static class ClockHelpers {
public static double NormalizedMean(this ICollection<double> values)
{
if (values.Count == 0)
return double.NaN;
var deviations = values.Deviations().ToArray();
var meanDeviation = deviations.Sum(t => Math.Abs(t.Item2)) / values.Count;
return deviations.Where(t => t.Item2 > 0 || Math.Abs(t.Item2) <= meanDeviation).Average(t => t.Item1);
}
public static IEnumerable<Tuple<double, double>> Deviations(this ICollection<double> values)
{
if (values.Count == 0)
yield break;
var avg = values.Average();
foreach (var d in values)
yield return Tuple.Create(d, avg - d);
}
}
Raw
gist-6647474.csproj
<?xml version="1.0" encoding="utf-8"?>
<Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
<PropertyGroup>
<Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
<Platform Condition=" '$(Platform)' == '' ">x86</Platform>
<ProductVersion>8.0.30703</ProductVersion>
<SchemaVersion>2.0</SchemaVersion>
<ProjectGuid>{F0A32394-4E4A-46B6-8AD0-B50B30B49D41}</ProjectGuid>
<OutputType>Exe</OutputType>
<RootNamespace>gist6647474</RootNamespace>
<AssemblyName>gist-6647474</AssemblyName>
</PropertyGroup>
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|x86' ">
<DebugSymbols>true</DebugSymbols>
<DebugType>full</DebugType>
<Optimize>false</Optimize>
<OutputPath>bin\Debug</OutputPath>
<DefineConstants>DEBUG;</DefineConstants>
<ErrorReport>prompt</ErrorReport>
<WarningLevel>4</WarningLevel>
<Externalconsole>true</Externalconsole>
<PlatformTarget>x86</PlatformTarget>
</PropertyGroup>
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|x86' ">
<DebugType>full</DebugType>
<Optimize>true</Optimize>
<OutputPath>bin\Release</OutputPath>
<ErrorReport>prompt</ErrorReport>
<WarningLevel>4</WarningLevel>
<Externalconsole>true</Externalconsole>
<PlatformTarget>x86</PlatformTarget>
</PropertyGroup>
<ItemGroup>
<Reference Include="System" />
</ItemGroup>
<ItemGroup>
<Compile Include="Program.cs" />
<Compile Include="BruteForce.cs" />
<Compile Include="SieveOfAtkin.cs" />
<Compile Include="SieveOfEratosthenes.cs" />
<Compile Include="SieveOfSundaram.cs" />
<Compile Include="Clock.cs" />
</ItemGroup>
<Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
<ProjectExtensions>
<MonoDevelop>
<Properties>
<Policies>
<TextStylePolicy inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/plain" />
<CSharpFormattingPolicy IndentSwitchBody="True" AutoPropertyFormatting="ForceOneLine" NamespaceBraceStyle="EndOfLine" ClassBraceStyle="EndOfLine" InterfaceBraceStyle="EndOfLine" StructBraceStyle="EndOfLine" EnumBraceStyle="EndOfLine" MethodBraceStyle="EndOfLine" ConstructorBraceStyle="EndOfLine" DestructorBraceStyle="EndOfLine" ElseNewLinePlacement="DoNotCare" CatchNewLinePlacement="NewLine" FinallyNewLinePlacement="NewLine" EmbeddedStatementPlacement="SameLine" ArrayInitializerWrapping="DoNotChange" ArrayInitializerBraceStyle="NextLine" BeforeMethodDeclarationParentheses="False" BeforeMethodCallParentheses="False" BeforeConstructorDeclarationParentheses="False" BeforeIndexerDeclarationBracket="False" BeforeDelegateDeclarationParentheses="False" NewParentheses="False" SpacesBeforeBrackets="False" SpacesAfterTypecast="True" NewLineAferMethodDeclarationOpenParentheses="SameLine" inheritsSet="Mono" inheritsScope="text/x-csharp" scope="text/x-csharp" />
<DotNetNamingPolicy DirectoryNamespaceAssociation="None" ResourceNamePolicy="FileName" />
<TextStylePolicy inheritsSet="VisualStudio" inheritsScope="text/plain" scope="application/xml" />
<XmlFormattingPolicy inheritsSet="Mono" inheritsScope="application/xml" scope="application/xml" />
<TextStylePolicy inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/x-csharp" />
<NameConventionPolicy>
<Rules>
<NamingRule Name="Namespaces" AffectedEntity="Namespace" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Types" AffectedEntity="Class, Struct, Enum, Delegate" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Interfaces" AffectedEntity="Interface" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
<RequiredPrefixes>
<String>I</String>
</RequiredPrefixes>
</NamingRule>
<NamingRule Name="Attributes" AffectedEntity="CustomAttributes" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
<RequiredSuffixes>
<String>Attribute</String>
</RequiredSuffixes>
</NamingRule>
<NamingRule Name="Event Arguments" AffectedEntity="CustomEventArgs" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
<RequiredSuffixes>
<String>EventArgs</String>
</RequiredSuffixes>
</NamingRule>
<NamingRule Name="Exceptions" AffectedEntity="CustomExceptions" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
<RequiredSuffixes>
<String>Exception</String>
</RequiredSuffixes>
</NamingRule>
<NamingRule Name="Methods" AffectedEntity="Methods" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Static Readonly Fields" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Protected, Public" NamingStyle="PascalCase" IncludeInstanceMembers="False" IncludeStaticEntities="True" />
<NamingRule Name="Fields (Non Private)" AffectedEntity="Field" VisibilityMask="Internal, Protected, Public" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="ReadOnly Fields (Non Private)" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Protected, Public" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="False" />
<NamingRule Name="Fields (Private)" AffectedEntity="Field, ReadonlyField" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
<AllowedPrefixes>
<String>_</String>
<String>m_</String>
</AllowedPrefixes>
</NamingRule>
<NamingRule Name="Static Fields (Private)" AffectedEntity="Field" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True" />
<NamingRule Name="ReadOnly Fields (Private)" AffectedEntity="ReadonlyField" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
<AllowedPrefixes>
<String>_</String>
<String>m_</String>
</AllowedPrefixes>
</NamingRule>
<NamingRule Name="Constant Fields" AffectedEntity="ConstantField" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Properties" AffectedEntity="Property" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Events" AffectedEntity="Event" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Enum Members" AffectedEntity="EnumMember" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Parameters" AffectedEntity="Parameter" VisibilityMask="VisibilityMask" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
<NamingRule Name="Type Parameters" AffectedEntity="TypeParameter" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
<RequiredPrefixes>
<String>T</String>
</RequiredPrefixes>
</NamingRule>
</Rules>
</NameConventionPolicy>
</Policies>
</Properties>
</MonoDevelop>
</ProjectExtensions>
<ItemGroup>
<Folder Include="Properties\" />
</ItemGroup>
</Project>
Raw
Program.cs
using System;
namespace gist6647474 {
class MainClass {
public static void Main(string[] args) {
Clock.BenchmarkCpu(action: () => {
var bruteForce = Primes.BruteForcePrimes(1000).GetEnumerator();
int count = 0, sum = 0;
while (bruteForce.MoveNext()) {
sum += bruteForce.Current;
count++;
}
//Console.Out.WriteLine("Brute Force: count={0} sum={1}", count, sum);
}, iterations: 10);
Clock.BenchmarkCpu(action: () => {
var eratosthenes = Primes.SieveOfEratosthenesPrimes(1000).GetEnumerator();
int count = 0, sum = 0;
while (eratosthenes.MoveNext()) {
sum += eratosthenes.Current;
count++;
}
//Console.Out.WriteLine("Sieve of Eratosthenes: count={0} sum={1}", count, sum);
}, iterations: 10);
Clock.BenchmarkCpu(action: () => {
var sundaram = Primes.SieveOfSundaramPrimes(1000).GetEnumerator();
int count = 0, sum = 0;
while (sundaram.MoveNext()) {
sum += sundaram.Current;
count++;
}
//Console.Out.WriteLine("Sieve of Sundaram: count={0} sum={1}", count, sum);
}, iterations: 10);
Clock.BenchmarkCpu(action: () => {
var atkin = Primes.SieveOfAtkinPrimes(1000).GetEnumerator();
int count = 0, sum = 0;
while (atkin.MoveNext()) {
sum += atkin.Current;
count++;
}
//Console.Out.WriteLine("Sieve of Atkin: count={0} sum={1}", count, sum);
}, iterations: 10);
}
}
}
Raw
SieveOfAtkin.cs
using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
public partial class Primes
{
public static IEnumerable<int> SieveOfAtkinPrimes(int max) {
if (max < 2) yield break;
yield return 2;
yield return 3;
BitArray isPrime = new BitArray(max + 1, false);
int squareRoot = (int) Math.Sqrt(max);
int xSquare = 1, xStepsize = 3;
int ySquare = 1, yStepsize = 3;
int computedVal = 0;
for (int x = 1; x <= squareRoot; x++) {
ySquare = 1;
yStepsize = 3;
for (int y = 1; y <= squareRoot; y++) {
computedVal = (xSquare << 2) + ySquare;
if ((computedVal <= max) && (computedVal % 12 == 1 || computedVal % 12 == 5)) isPrime[computedVal] = !isPrime[computedVal];
computedVal -= xSquare;
if ((computedVal <= max) && (computedVal % 12 == 7)) isPrime[computedVal] = !isPrime[computedVal];
if (x > y) {
computedVal -= ySquare << 1;
if ((computedVal <= max) && (computedVal % 12 == 11)) isPrime[computedVal] = !isPrime[computedVal];
}
ySquare += yStepsize;
yStepsize += 2;
}
xSquare += xStepsize;
xStepsize += 2;
}
for (int n = 5; n <= squareRoot; n++) {
if (isPrime[n]) {
int k = n * n;
for (int z = k; z <= max; z += k) isPrime[z] = false;
}
}
for (int i = 3; i < max; i++) {
if (isPrime[i]) yield return i;
}
}
}
Raw
SieveOfEratosthenes.cs
using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
public partial class Primes
{
public static IEnumerable<int> SieveOfEratosthenesPrimes (int max)
{
if (max < 2) yield break;
BitArray primeList = new BitArray (max + 1, true);
for (int candidate = 2; candidate <= max; candidate++) {
if (primeList [candidate]) {
for (int multiples = 2; (multiples * candidate) < max; multiples++) {
primeList [multiples * candidate] = false;
}
yield return candidate;
}
}
}
}
Raw
SieveOfSundaram.cs
using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
public partial class Primes
{
public static IEnumerable<int> SieveOfSundaramPrimes (int max)
{
if (max < 2) yield break;
yield return 2;
int maxVal = 0;
int denominator = 0;
BitArray primeList = new BitArray(max + 1, true);
for (int i = 1; i < max; i++) {
denominator = (i << 1) + 1;
maxVal = (max - i) / denominator;
for (int j = i; j <= maxVal; j++) {
primeList[i + j * denominator] = false;
}
}
int prime = 0;
for (int i = 1; i < max; i++) {
if (primeList[i]) {
prime = (i << 1) + 1;
yield return prime;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment