File: ./go.mod
   1 module primes
   2 
   3 go 1.18

     File: ./main.go
   1 package main
   2 
   3 import (
   4     "bufio"
   5     "math"
   6     "os"
   7     "strconv"
   8 )
   9 
  10 const helpMsg = `primes [count...]
  11 
  12 Find the first n prime numbers, where the default is 1 million, showing
  13 each in its own line.
  14 `
  15 
  16 func main() {
  17     if len(os.Args) < 2 {
  18         run(1_000_000)
  19         return
  20     }
  21 
  22     switch os.Args[1] {
  23     case `-h`, `--h`, `-help`, `--help`:
  24         os.Stderr.WriteString(helpMsg)
  25         return
  26     }
  27 
  28     f, err := strconv.ParseFloat(os.Args[1], 64)
  29     if err != nil || math.IsInf(f, 0) || math.IsNaN(f) {
  30         const msg = "\x1b[31mgiven invalid number of primes\x1b[0m\n"
  31         os.Stderr.WriteString(msg)
  32         os.Exit(1)
  33     }
  34 
  35     run(int(f))
  36 }
  37 
  38 func run(n int) {
  39     // buffering the output minimizes actual output requests to the system,
  40     // which in turn results in major speed-ups
  41     w := bufio.NewWriter(os.Stdout)
  42     defer w.Flush()
  43 
  44     // assume all errors are caused by a closed stdout pipe, so quit
  45     // the app right away without complaining, by ignoring errors
  46     primes(w, n)
  47 }
  48 
  49 // primes emits the first n prime numbers, just for fun
  50 func primes(w *bufio.Writer, n int) error {
  51     // 2 is the only even prime number
  52     if n > 0 {
  53         emitLine(w, 2)
  54         n--
  55     }
  56 
  57     // all other primes are odd numbers
  58     for v := uint64(3); n > 0; v += 2 {
  59         if isPrime(v) {
  60             err := emitLine(w, v)
  61             if err != nil {
  62                 return err
  63             }
  64             n--
  65         }
  66     }
  67 
  68     return nil
  69 }
  70 
  71 // isPrime checks if the number given is prime, using the efficient algo,
  72 // where remainders are tested only up to the square root of the number
  73 // being tested for primality, thus resulting in O(n**0.5) time-complexity;
  74 // a naive approach using half/full loops would result in O(n) complexity
  75 // instead
  76 func isPrime(n uint64) bool {
  77     // numbers less than 2 aren't prime for sure
  78     if n < 2 {
  79         return false
  80     }
  81 
  82     // the only even prime is 2
  83     if n%2 == 0 {
  84         return n == 2
  85     }
  86 
  87     // use square-root as loop-limit for better algo
  88     max := uint64(math.Sqrt(float64(n)))
  89 
  90     // all primes after 2 are odd numbers
  91     for k := uint64(3); k <= max; k += 2 {
  92         if n%k == 0 {
  93             return false
  94         }
  95     }
  96 
  97     // it's a prime number when no full divisors were found, except for
  98     // 1 and the number itself
  99     return true
 100 }
 101 
 102 // emitLine outputs a line with the number given
 103 func emitLine(w *bufio.Writer, n uint64) error {
 104     // only up to 21 digits are needed for any stringified uint64
 105     // echo '2^64' | bc | wc -c
 106     var buf [24]byte
 107     w.Write(strconv.AppendUint(buf[:0], n, 10))
 108     return w.WriteByte('\n')
 109 }