As mentioned previously at Kosong Satu Network, our tech team initiate a daily challenge for fun to exercise our programming logic with a dead simple problem.

One of the challenge that we have previously was prime number functionality, it should be able to do the following:

  1. Test if a number is prime number and return the reason when it’s not
  2. Get the first n prime numbers
  3. Get list of prime numbers between x and y

Here are the solution I’ve come up with in Go and almost equivalent code in javascript (+mocha) :

source: prime.go 

package main

import (
    "fmt"
    "math"
)

const Min = 2

type Prime struct{}

func (p Prime) Is(n int) error {
    if n < Min {
        return fmt.Errorf("prime must be integer greater than %d", Min)
    }

    divider := int(math.Floor(math.Sqrt(float64(n))))
    for i := Min; i <= divider; i++ {
        if n%i == 0 {
            return fmt.Errorf("%d is divisor of %d", i, n)
        }
    }

    return nil
}

func (p Prime) First(n int) []int {
    var (
        r         []int = []int{}
        count     int   = 0
        iteration int   = Min
    )
    for count < n {
        if err := p.Is(iteration); err == nil {
            r = append(r, iteration)
            count++
        }
        iteration++
    }
    return r
}

func (p Prime) Between(x, y int) []int {
    var r []int = []int{}
    if x < Min {
        x = Min
    }

    for i := x; i <= y; i++ {
        if err := p.Is(i); err == nil {
            r = append(r, i)
        }
    }
    return r
}

test: prime_test.go

package main

import (
    "reflect"
    "strconv"
    "strings"
    "testing"
)

func int_to_string_arrays(a []int) []string {
    r := []string{}
    for _, v := range a {
        r = append(r, strconv.Itoa(v))
    }
    return r
}

func TestIsPrime(t *testing.T) {
    type PrimeData struct {
        number int
        reason string
    }
    var primes []PrimeData = []PrimeData{
        {
            number: 1,
            reason: "prime must be integer greater than 2",
        },
        {
            number: 2,
        },
        {
            number: 3,
        },
        {
            number: 9,
            reason: "3 is divisor of 9",
        },
        {
            number: 11,
        },
        {
            number: 12,
            reason: "2 is divisor of 12",
        },
        {
            number: 13,
        },
    }
    prime := Prime{}
    for _, v := range primes {
        expected := (len(v.reason) == 0)
        err := prime.Is(v.number)
        if err != nil && expected {
            t.Errorf("%d expected true got false", v.number)
        }
        if !expected && err.Error() != v.reason {
            t.Errorf("%d expected %s got %s", v.number, v.reason, err.Error())
        }
    }
}

func TestFirstPrimes(t *testing.T) {
    prime := Prime{}
    first_count := 5
    expected := []int{2, 3, 5, 7, 11}
    primes := prime.First(first_count)
    if !reflect.DeepEqual(expected, primes) {
        t.Errorf("first %d primes expected %s got %s",
            first_count,
            strings.Join(int_to_string_arrays(expected), ","),
            strings.Join(int_to_string_arrays(primes), ","))
    }

}

func TestBetweenPrimes(t *testing.T) {
    prime := Prime{}
    x, y := 1, 15
    expected := []int{2, 3, 5, 7, 11, 13}
    primes := prime.Between(x, y)
    if !reflect.DeepEqual(expected, primes) {
        t.Errorf("between %d - %d primes expected %s got %s",
            x,
            y,
            strings.Join(int_to_string_arrays(expected), ","),
            strings.Join(int_to_string_arrays(primes), ","))
    }
}

test result:

➜  primes git:(master) go test
PASS
ok      _/chazzuka/challenges/primes    0.006s

source: prime.js

'use strict';
var min = 2;
var reason = (function() {
    var m = '';
    return {
        set: function(r) {
            m = r;
        },
        get: function() {
            return m;
        },
        reset: function() {
            m = '';
        },
    };
})();

var is = function(n) {
    if (n < min) {
        reason.set('prime must be integer greater than 2');
        return false;
    }

    var sqrt = Math.floor(Math.sqrt(n));
    for (var i = min; i <= sqrt; i++) {
        if (n % i === 0) {
            reason.set(i + ' is divisor of ' + n);
            return false;
        }
    }

    reason.reset();
    return true;
}

var first = function(n) {
    var x = min,
        y = 0,
        r = [];
    while (y < n) {
        if (is(x)) {
            r.push(x);
            y++;
        }
        x++;
    }
    return r;
}

var between = function(x, y) {
    var r = [];
    for (var i = x; i <= y; i++) {
        if (is(i)) r.push(i);
    }
    return r;
}

var why = function() {
    return reason.get();
}


exports.is = is;
exports.first = first;
exports.between = between;
exports.why = why;

source: test.js

const prime = require('./prime');
const assert = require('assert');

describe('prime', function() {
    describe('#is', function() {
        it('should detect if a number is prime or not and giving a reason when it is not', function() {
            var primes = [{
                number: 1,
                expected: false,
                reason: 'prime must be integer greater than 2',
            }, {
                number: 2,
                expected: true,
            }, {
                number: 3,
                expected: true,
            }, {
                number: 9,
                expected: false,
                reason: '3 is divisor of 9',
            }, {
                number: 11,
                expected: true,
            }, {
                number: 12,
                expected: false,
                reason: '2 is divisor of 12',
            }, {
                number: 13,
                expected: true,
            }, ];
            for (var i = 0; i < primes.length; i++) {
                var o = primes[i]
                assert.equal(prime.is(o.number), o.expected);
                if (!o.expected) {
                    assert.equal(prime.why(), o.reason);
                }
            }
        });
    });

    describe('#first', function() {
        it('should giving the first n of prime numbers', function() {
            var primes = prime.first(5);
            assert.equal(primes.length, 5);
            assert.deepEqual(primes, [2,3,5,7,11]);
        });
    });

    describe('#between', function() {
        it('should giving the array of prime numbers between x,y', function() {
            var primes = prime.between(1,15);
            assert.equal(primes.length, 6);
            assert.deepEqual(primes, [2,3,5,7,11,13]);
        });
    });
});

test result:

➜  primes git:(master) mocha
    prime
    #is
      ✓ should detect if a number is prime or not and giving a reason when it is not
    #first
      ✓ should giving the first n of prime numbers
    #between
      ✓ should giving the array of prime numbers between x,y


    3 passing (12ms)

Spread the word

© 2015 Komang. All Rights Reserved.

Made with in Kuta, Bali, Indonesia

Proudly published with Hugo