Prime Generation in Go

Question

EDIT . The question basically involves getting primes to a certain limit. An initial question follows.

I want my if become true if only these two conditions are true:

 for i := 2; i <= 10; i++ { if i%i == 0 && i%1 == 0 { } else { } } 

In this case, all possible numbers pass by these conditions, but I want only numbers 2, 3, 5, 7, 11 ... basically numbers that are divisible only by themselves and by 1 in order to pass, except being the very first " 2 ". How can i do this?

thanks

Answer 1

You seem to be looking for prime numbers . However, the conditions you described are not sufficient. In fact, you need to use an algorithm to generate them (perhaps to a certain limit).

This is an implementation of the Atkin Sieve which is an optimized variation of the ancient sieve of eratosthenes.

Demo: http://play.golang.org/p/XXiTIpRBAu

For completeness:

 package main import ( "fmt" "math" ) // Only primes less than or equal to N will be generated const N = 100 func main() { var x, y, n int nsqrt := math.Sqrt(N) is_prime := [N]bool{} for x = 1; float64(x) <= nsqrt; x++ { for y = 1; float64(y) <= nsqrt; y++ { n = 4*(x*x) + y*y if n <= N && (n%12 == 1 || n%12 == 5) { is_prime[n] = !is_prime[n] } n = 3*(x*x) + y*y if n <= N && n%12 == 7 { is_prime[n] = !is_prime[n] } n = 3*(x*x) - y*y if x > y && n <= N && n%12 == 11 { is_prime[n] = !is_prime[n] } } } for n = 5; float64(n) <= nsqrt; n++ { if is_prime[n] { for y = n * n; y < N; y += n * n { is_prime[y] = false } } } is_prime[2] = true is_prime[3] = true primes := make([]int, 0, 1270606) for x = 0; x < len(is_prime)-1; x++ { if is_prime[x] { primes = append(primes, x) } } // primes is now a slice that contains all primes numbers up to N // so let print them for _, x := range primes { fmt.Println(x) } } 

Answer 2

Here is the golang sieve of Eratosthenes

 package main import "fmt" // return list of primes less than N func sieveOfEratosthenes(N int) (primes []int) { b := make([]bool, N) for i := 2; i < N; i++ { if b[i] == true { continue } primes = append(primes, i) for k := i * i; k < N; k += i { b[k] = true } } return } func main() { primes := sieveOfEratosthenes(100) for _, p := range primes { fmt.Println(p) } } 

Answer 3

The easiest way to get "numbers that are divisible only by themselves and by 1", which is also known as prime numbers: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

This is not a “simple statement."

Answer 4

If you don't mind the very small chance (9.1e-13 in this case) that they are not simple, you can use ProbablyPrime from math / big , like this ( play )

 import ( "fmt" "math/big" ) func main() { for i := 2; i < 1000; i++ { if big.NewInt(int64(i)).ProbablyPrime(20) { fmt.Printf("%d is probably prime\n", i) } else { fmt.Printf("%d is definitely not prime\n", i) } } } 

Just change the constant 20 as you like, that they are simple.

Answer 5

Easy way (fixed):

 package main import "math" const n = 100 func main() { print(1, " ", 2) L: for i := 3; i <= n; i += 2 { m := int(math.Floor(math.Sqrt(float64(i)))) for j := 2; j <= m; j++ { if i%j == 0 { continue L } } print(" ", i) } } 

Answer 6

just change 100 in the outer loop to the limit of the prime number you want to find. Hooray!!

  for i:=2; i<=100; i++{ isPrime:=true for j:=2; j<i; j++{ if i % j == 0 { isPrime = false } } if isPrime == true { fmt.Println(i) } } } 

Answer 7

Here, try this by checking all the corner cases and the optimized way to find your numbers and run the logic when the function returns true.

 package main import ( "math" "time" "fmt" ) func prime(n int) bool { if n < 1 { return false } if n == 2 { return true } if n % 2 == 0 && n > 2 { return false } var maxDivisor = int(math.Floor(math.Sqrt(float64 (n)))) //d := 3 for d:=3 ;d <= 1 + maxDivisor; d += 2 { if n%d == 0 { return false } } return true } //======Test Function===== func main() { // var t0 = time.Time{} var t0= time.Second for i := 1; i <= 1000; i++ { fmt.Println(prime(i)) } var t1= time.Second println(t1 - t0) } 

Answer 8

 package main import ( "fmt" ) func main() { //runtime.GOMAXPROCS(4) ch := make(chan int) go generate(ch) for { prime := <-ch fmt.Println(prime) ch1 := make(chan int) go filter(ch, ch1, prime) ch = ch1 } } func generate(ch chan int) { for i := 2; ; i++ { ch <- i } } func filter(in, out chan int, prime int) { for { i := <-in if i%prime != 0 { out <- i } } }