extends Node

const LIMIT: int = 25000

func _ready() -> void:
	var start_time: int = Time.get_ticks_msec()
	var prime_count: int = count_primes(LIMIT)
	var end_time: int = Time.get_ticks_msec()
	var duration: int = end_time - start_time
	prints("Number of primes found:", prime_count)
	prints("Time taken:", duration, "ms")

func count_primes(limit: int) -> int:
	if limit <= 2:
		return 0 if limit < 2 else 1
	var sieve: PackedByteArray = PackedByteArray()
	sieve.resize((limit + 1) >> 1)
	sieve.fill(1)
	var count: int = 1
	var num: int = 3
	var sqrt_limit: int = sqrt(limit) as int

	while num <= sqrt_limit:
		if sieve[num >> 1] == 1:
			var multiple: int = num * num
			while multiple < limit:
				sieve[multiple >> 1] = 0
				multiple += num << 1
			count += 1
		num += 2
	while num < limit:
		count += sieve[num >> 1]
		num += 2
	return count