Show all primes in go

Question

I'm trying to go through Adrian simple programming tasks; Elementary task 8 It's basically asking for an infinite loop to print every prime number as it finds it.

Are there too many if statements? Call it intuitive knowledge, but something is just bugging me, like I'm missing something. Like, I can remove one of the if statements. So I'm wondering what you guys will find.

package main

import "fmt"

func main() {
    var current_prime int
    var prime bool
    current_prime = 0

    for {
        prime = true
        current_prime++

        for i := 2; i < current_prime; i++ {
            if current_prime % i == 0 {
                prime = false
                i = current_prime
            }
        }

        if prime {
            fmt.Println("found prime:", current_prime);
        }
    }
}

Answer 1

Simple Programming Problems

Write a program that prints all prime numbers. (Note: if your programming language does not support arbitrary size numbers, printing all primes up to the largest number you can easily represent is fine too.)

---

Your program says one is prime. That is not correct.

The only even prime number is two. You don't appear take advantage of that. That is inefficient.

A number can only be divisible by a number less than or equal to its square root. You don't appear take advantage of that. That is inefficient.

You are asked to "[print] all primes up to the largest number you can easily represent." In Go, type int is either 32 or 64 bits. You don't guarantee the largest number by using type int64. Your program is not correct.

You have no program termination condition. Your program is not correct.

And so on.

---

For example, fixing your code,

package main

import (
    "fmt"
    "math"
)

func main() {
    fmt.Println("prime numbers:")
    fmt.Println(2)

    for n := int64(3); n > 0; n += 2 {
        prime := true

        r := int64(math.Sqrt(float64(n))) + 1
        for i := int64(3); i < r; i += 2 {
            if n%i == 0 {
                prime = false
                break
            }
        }

        if prime {
            fmt.Println(n)
        }
    }
}

---

To provide a measure of performance, the results from a Go benchmark for all prime numbers up to 32,771:

BenchmarkPeterSO-4           500       2661556 ns/op
BenchmarkIbnRushd-4            3     492864429 ns/op

Answer 2

Instead of trying to get a performance increase with a faster solution let's review your program and try to make it a solid one.

The variables

var current_prime int
var prime bool
current_prime = 0

Check this example:

var a int = 0 // 0
var b int     // default int value is 0, similar to above
var c = 0     // type is int, similar to above
d := 0        // same

The latter is short and nice, I suggest you to stick to it. var notation is required in package block (globals), when explicit type is needed and to overcome variable shading.

You've declared the prime variable, but is first used only within the outer loop, so declare it there. Try to introduce new variables first time you need them.

The outer loop

for {
    // ...
}

Your for loop is infinite since there is no loop condition or a break statement. The current_prime will overflow and you'll start printing the same/wrong numbers.

As pointed by peterSO, the first prime number is 2, so we can start with it.

for current_prime := 2; i > 0; i++ {
    // ...
}

When overflow occurs the loop condition will be falsy and the loop will terminate.

To take it further it is better not to expect int overflow and use MaxInt* constants from math package. Apart from guaranteed proper uint overflow there is nothing solid about int, so it is better not to abuse its behavior.

The inner loop

for i := 2; i < current_prime; i++ {
    if current_prime % i == 0 {
        prime = false
        i = current_prime
    }
}

It took me a while to understand the purpose of i = current_prime line. No. This is not nice, use break to end the loop.

This one is much cleaner to me:

for i := 2; i < current_prime; i++ {
    if current_prime % i == 0 {
        prime = false
        break
    }
}

Let's take it further. After the inner loop you test the prime variable and print the current_prime number. So when you get current_prime % i == 0 as true you already know current_prime is not a prime number and you need to continue the outer loop. For such purpose Golang has labels that perfectly solve the task:

outer:
    for prime := 2; prime > 0; prime++ {
        for i := 2; i < prime; i++ {
            if prime % i == 0 {
                continue outer
            }
        }
        fmt.Println(prime)
    }

A continue outer statement will break the inner loop and continue the outer one. When you place a label one line before the loop you may break and continue right to it. It helps escaping nested loops a lot.

Finally lets choose the appropriate types for our task. Since we don't need the signed numbers we can use uint instead of int. Better, lets use uint64 directly to guaranty the maximum available type. The nice thing about unsigned numbers is that Golang guarantees that they will overflow properly so we can check for zero value to terminate the loop.

Example rewrite

Here follows a possible rewrite of your original program:

package main

import "fmt"

func main() {

outer:
    for prime := uint64(2); prime > 0; prime++ {
        for i := uint64(2); i < prime; i++ {
            if prime % i == 0 {
                continue outer
            }
        }
        fmt.Println(prime)
    }
}

Things accomplished:

• proper types are used
• overflow is handled
• no hacks