atkin.jl

#!/usr/bin/env julia


#=
 # Algoritmos para calcular numeros primos.
 #
 # author: Ismael Venegas Castelló
 # date: Enero del 2015
=#


module Cribas

export atkin


@doc """
    Criba de Atkin: http://es.wikipedia.org/wiki/Criba_de_Atkin
    """ ->
function atkin(limite::Integer = 0)
    @inbounds begin
        primos = Int[2, 3]
        dos = primos[1]

        if limite < 0
            error("ERROR: la dimensión no debe ser negativa (se encontro $(limite))")

        elseif 0 <= limite < dos
            return Int[]

        elseif limite == dos
            return primos[1:1]

        else
            factor = int(sqrt(limite))
            criba = falses(limite)

            for x in [1:factor]
                for y in [1:factor]
                    n = 4x^2 + y^2
                    if n <= limite && (n % 12 == 1 || n % 12 == 5)
                        criba[n] = !criba[n]
                    end

                    n = 3x^2 + y^2
                    if n <= limite && n % 12 == 7
                        criba[n] = !criba[n]
                    end

                    n = 3x^2 - y^2
                    if x > y && n <= limite && n % 12 == 11
                        criba[n] = !criba[n]
                    end
                end
            end

            for x in [3:factor]
                if criba[x]
                    for y in [x^2:x^2:limite]
                        criba[y] = false
                    end
                end
            end

            for i in [5:limite]
                if criba[i]
                    push!(primos, i)
                end
            end
        end

        return primos
    end
end

atkin(limite::FloatingPoint) = atkin(int(trunc(limite)))
atkin(limite::String) = atkin(float(limite))


end