Prime counting microbenchmark

primes.gd

extends Node2D

func _ready() -> void:
	var max: int = 25000
	
	var start: int = Time.get_ticks_usec()
	var result_is_prime: int = count_is_prime(max)
	var end: int = Time.get_ticks_usec()
	var time_is_prime: int = end - start
	
	start = Time.get_ticks_usec()
	var result_sieve: int = count_sieve(max)
	end = Time.get_ticks_usec()
	var time_sieve: int = end - start
	
	assert(result_is_prime == result_sieve)
	print(result_is_prime, " prime numbers below ", max)
	print("is_prime: ", time_is_prime, "us")
	print("sieve:    ", time_sieve, "us")

func limit(max: int) -> int:
	var root = sqrt(float(max))
	return ceili(root) + 1

func is_prime(n: int) -> bool:
	var limit: int = limit(n)
	var i: int = 2
	while i <= limit:
		if n % i == 0:
			return false

		i += 1
	
	return true

func count_is_prime(max: int) -> int:
	var primes: int = 0
	var n: int = 0
	while n < max:
		if is_prime(n):
			primes += 1
		
		n += 1
	
	return primes

func sieve(max: int) -> PackedByteArray:
	var sieve: PackedByteArray = PackedByteArray()
	sieve.resize(max)
	sieve.fill(1)
	
	var limit: int = limit(max)
	var n: int = 2
	while n <= limit:
		if sieve[n] != 1:
			n += 1
			continue
		
		var multiple: int = n * 2
		while multiple < max:
			sieve[multiple] = 0
			multiple += n

		n += 1
	
	return sieve

func count_sieve(max: int) -> int:
	var sieve: PackedByteArray = sieve(max)
	
	var primes: int = 0
	var n: int = 2
	while n < max:
		if sieve[n] == 1:
			primes += 1
		
		n += 1
	
	return primes