Instantly share code, notes, and snippets.

# dazfuller/primes.go Created Oct 23, 2012

What would you like to do?
A solution to Project Euler problem 7
 package primes import ( "container/list" "math" ) // Simple function for checking if a value coming in on a channel is divisible by a // divisor, if it is then it is passed to the output channel func checkDivisor(divisor int64, in chan int64, out chan int64) { for { val := <-in if val % divisor != 0 { out <- val } } } // A simple sieve implementation func PrimeSieveOfErat(end int64) []int64 { if end < int64(2) { return make([]int64, 0) } ar := make([]bool, end) ar[0] = true ar[1] = true limit := int64(math.Sqrt(float64(end))) + int64(1) for i := int64(2); i < limit; i++ { if ar[i] == false { for j := i * 2; j < end; j += i { ar[j] = true } } } count := 0 for _, v := range ar { if v == false { count++ } } result := make([]int64, count) index := int64(0) for i, v := range ar { if v == false { result[index] = int64(i) index++ } } return result } // Determnes if a number is prime by check to see if it is evenly divisible // by a supplied list of prime numbers func isPrime(n int64, primes *list.List) bool { if primes == nil { return false } for e := primes.Front(); e != nil; e = e.Next() { if n % e.Value.(int64) == 0 { return false } } return true } // Gets the Nth prime number func GetNthPrime(n int64) int64 { primes := list.New() primes.PushBack(int64(2)) for i := int64(3); int64(primes.Len()) < n; i += int64(2) { if isPrime(i, primes) { primes.PushBack(i) } } return primes.Back().Value.(int64) } // Creates a prime sieve func MakePrimeSieve() chan int64 { // Initial seed channel seed := make(chan int64) // Channel to return to the caller primeCh := make(chan int64, 10) // Add "2" to the return channel as we know this is a prime and the only even one primeCh <- 2 // Create a goroutine to add values to the seed channel go func() { for i := int64(3); ; i += 2 { seed <- i } }() // Create the output channel and create the first divisor goroutine to check for division by 2 output := make(chan int64) go checkDivisor(2, seed, output) // Create a new go routine for processing prime numbers. When a new value is detected on the output // channel then it has passed divisor checks and must be a prime number, so a new goroutine is created // whose input is the output of the last goroutine. And so each new detected prime results in a new // divisor check go func() { for { prime := <-output primeCh <- prime input := output output = make(chan int64) go checkDivisor(prime, input, output) } }() return primeCh } // Determines the prime factors for a given value, returning a map of prime values and the number of // times each is used func PrimeFactors(value int64) map[int64]int64 { ps := MakePrimeSieve() prime := <-ps result := make(map[int64]int64) for value != 1 { for value % prime == 0 { if _, ok := result[prime]; ok == false { result[prime] = 1 } else { result[prime] += 1 } value /= prime } prime = <-ps } return result }
 package primes import "testing" func TestPrimeSieve(t *testing.T) { ps := MakePrimeSieve() var prime int64 for i := 0; i < 168; i++ { prime = <-ps } if prime != 997 { t.Error("Expected 997, got ", prime) } } func TestSieveOfErat(t *testing.T) { primes := PrimeSieveOfErat(10) expected := []int64 { 2, 3, 5, 7 } if len(primes) != len(expected) { t.Error("Expected number of primes 4, got ", len(primes)) return } for i, v := range expected { if v != primes[i] { t.Error("Unexpected prime ", primes[i]) break } } } func TestGetNthPrime(t *testing.T) { v := GetNthPrime(100) if v != 541 { t.Error("Expected 541, got ", v) } } func TestPrimeFactors(t *testing.T) { pf := PrimeFactors(288) if val, ok := pf[2]; ok == false || val != 5 { t.Error("Expected 2^5, got ", pf) } if val, ok := pf[3]; ok == false || val != 2 { t.Error("Expected 3^2, got ", pf) } }
 package main import ( "euler/primes" "fmt" "math" ) func getUpperLimit(nthPrime int) int64 { n := float64(nthPrime) x := n * math.Log(n) * 1.2 return int64(x) } func main() { pn := primes.PrimeSieveOfErat(getUpperLimit(10001)) fmt.Println(pn[10000]) }
 // Simple function for checking if a value coming in on a channel is divisible by a // divisor, if it is then it is passed to the output channel func checkDivisor(divisor int64, in chan int64, out chan int64) { for { val := <-in if val % divisor != 0 { out <- val } } } // Creates a prime sieve func MakePrimeSieve() chan int64 { // Initial seed channel seed := make(chan int64) // Channel to return to the caller primeCh := make(chan int64, 10) // Add "2" to the return channel as we know this is a prime and the only even one primeCh <- 2 // Create a goroutine to add values to the seed channel go func() { for i := int64(3); ; i += 2 { seed <- i } }() // Create the output channel and create the first divisor goroutine to check for division by 2 output := make(chan int64) go checkDivisor(2, seed, output) // Create a new go routine for processing prime numbers. When a new value is detected on the output // channel then it has passed divisor checks and must be a prime number, so a new goroutine is created // whose input is the output of the last goroutine. And so each new detected prime results in a new // divisor check go func() { for { prime := <-output primeCh <- prime input := output output = make(chan int64) go checkDivisor(prime, input, output) } }() return primeCh }
 // Determnes if a number is prime by check to see if it is evenly divisible // by a supplied list of prime numbers func isPrime(n int64, primes *list.List) bool { if primes == nil { return false } for e := primes.Front(); e != nil; e = e.Next() { if n % e.Value.(int64) == 0 { return false } } return true } // Gets the Nth prime number func GetNthPrime(n int64) int64 { primes := list.New() primes.PushBack(int64(2)) for i := int64(3); int64(primes.Len()) < n; i += int64(2) { if isPrime(i, primes) { primes.PushBack(i) } } return primes.Back().Value.(int64) }
 // A simple sieve implementation func PrimeSieveOfErat(end int64) []int64 { if end < int64(2) { return make([]int64, 0) } ar := make([]bool, end) ar[0] = true ar[1] = true limit := int64(math.Sqrt(float64(end))) + int64(1) for i := int64(2); i < limit; i++ { if ar[i] == false { for j := i * 2; j < end; j += i { ar[j] = true } } } count := 0 for _, v := range ar { if v == false { count++ } } result := make([]int64, count) index := int64(0) for i, v := range ar { if v == false { result[index] = int64(i) index++ } } return result }