Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating prime numbers in Go

Tags:

go

primes

EDIT: The question essentially asks to generate prime numbers up to a certain limit. The original question follows.

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

for i := 2; i <= 10; i++ {

    if i%i == 0 && i%1 == 0 {

    } else {

    }
}

In this case every possible number gets past these conditions, however I want only the numbers 2, 3, 5, 7, 11... basically numbers that are divisible only with themselves and by 1 to get past, with the exception being the very first '2'. How can I do this?

Thanks

like image 236
albind Avatar asked Feb 18 '14 12:02

albind


3 Answers

It seems you are looking for prime numbers. However the conditions you described are not sufficient. In fact you have to use an algorithm to generate them (up to a certain limit most probably).

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

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

For the sake of 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's print them
    for _, x := range primes {
        fmt.Println(x)
    }
}
like image 135
Agis Avatar answered Sep 28 '22 06:09

Agis


Here's a 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)
    }
}
like image 27
k107 Avatar answered Sep 28 '22 06:09

k107


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

It's not a "simple if statement".

like image 39
Art Avatar answered Sep 28 '22 06:09

Art