Faster Sieve of Eratosthenes in Make

Makefile

eq = $(filter $1,$2)

# List operations
slice = $(wordlist 2,$(words $1),$1)
map = $(if $2,$(call map,$1,$(call slice,$2),$3,$4 $(call $1,$(firstword $2),$3,$4)),$4)
rotate = $(call slice,$1) $(firstword $1)
zip = $(if $2,$(call zip,$1,$(call slice,$2),$(call rotate,$3),$4 $(call $1,$(firstword $2),$(firstword $3))),$4)
fold = $(if $2,$(call fold,$1,$(call slice,$2),$(call $1,$3,$(firstword $2),$2)),$3)
explode = $(if $(call eq,$(words $4),$1),$3,$(call explode,$1,$2,$3 $2,$(words $4) $4))

# Create range of numbers from 0..N-1
range = $(if $(call eq,$(words $2),$1),$2,$(call range,$1,$2 $(words $2)))

# Create a cycle
cycle = x $(call slice,$(call range,$1))

# Sift out factors of x
eliminate = $(if $(call eq,$2,x),_,$1)
sieve = $(call zip,eliminate,$2,$(call cycle,$1))

# Sieve of Eratosthenes
# If number is not removed, add it to list of primes and remove factors of it
eratosthenes = $(if $(call eq,$(firstword $2),$1),_$1 $(call slice,$(sieve)), $(call slice,$2))

# Create a list of N^2 elements
pow2 = $(call explode,$1,$(call explode,$1,_))

# Helper function to call our algorithm
dispatch = $(firstword $1)$(call eratosthenes,$2,$(call slice,$1))

# Find the integer square root of N
max = $(subst __,_,$(join $1,$2))
gte = $(filter-out $(words $2),$(words $(call max,$1,$2)))$(filter $(words $1),$(words $2))

find_limit = $(if $(filter-out $(firstword $1),$(words $(call slice,$1))),$1,\
	     $(if $(call gte,$(call pow2,$2),$(call slice,$1)),$2 $(call slice,$1),$1))

sqrt = $(firstword $(call fold,find_limit,$(call slice,$(call range,$1)),$1 $(call explode,$1,_)))

# Calculate the prime numbers below N
# We only need to iterate from 2 to sqrt(N)
numbers = $(call slice,$(call slice, $(call range,$1)))
primes_below = $(call slice,$(subst _, ,$(call fold,dispatch,$(wordlist 1,$(call sqrt,$1),$(numbers)),_1 $(numbers))))

println = $(info $1)

N ?= 1000

.PHONY: all
all: ; $(call map,println,$(call primes_below,$(N)))