Create a gist now

Instantly share code, notes, and snippets.

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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment