Help with prime numbers

ok I will make this clear and simple

I am trying to make a function that finds the first n prime numbers, the problem is I would have to do a loop and if N was a huge number then the loop would last longer making it less efficient

I am in school so that was my guess since I haven’t tried it out yet to see how fast it performs
my question is there a more efficient way then using a loop to find the first n prime numbers?

note: since I’m in school I can’t try any code so I’ll test later

1 Like

I can’t think of a way of doing it without doing a loop, but if you do every other number, since even numbers are never prime, you can make it efficient.

1 Like

I don’t know if this is more efficient than your current code, but I found its core in an article written for python that I adapted to roblox.

function getPrimes(n)
   local primes = {}
   
   for i = 2, n do
      local isPrime = i % 2 ~= 0 or i == 2 -- eliminates odd numbers excluding 2
      
      if isPrime then
         for k = 3, i do -- starts at 3 since we know it isn't even
            if i % k == 0 then -- checks divisibility
               isPrime = false
               
               break
            end
         end
      end
      
      if isPrime then
         table.insert(primes,i) -- adds prime to table
      end
   end
   
   return primes
end

If you are calling this function more than once, I would recommend implementing a prime number cache system, so it can easily access previously recorded primes without having to iterate inefficiently over ones that have already been regarded as prime.

Edit: This functions gives all the primes in the range 1-n, which I just realized is not what you’re asking for. You could apply a function similar to this into your code.

2 Likes

You can’t do every other number because 2 is prime

You can start the loop at 3 instead of 2 like @Galactiq did.

1 Like

The main way of including 2 was in this line also:

local isPrime = i % 2 ~= 0 or i == 2

The loop later on starting at 3 also prevents it from doind 2 % 2, which is 0.

I just made a function:

function IsPrime(Num)
	local Primes = {}
	for i = 1, Num, 1 do
		local PossibleFactor = Num/i
		if PossibleFactor % 1 == 0 then
			table.insert(Primes, PossibleFactor)
		end
		if #Primes > 2 then
			print("Composite")
			break
		end
	end
	if #Primes == 2 then
		print("Prime")
	end
end

IsPrime(11)

EDIT: Made it WAY more efficient.

I never asked for a prime number checker :joy:

Yeah… I kinda just realized that…

ok just making sure, thanks for helping tho

it is

I can implement a min/max system for it later
rn I just want it to be first 1-n prime numbers

Found a much simpler and smaller function:

 local function isPrime(n)
   for i = 2, n^(1/2) do
      if (n % i) == 0 then
         return false
      end
      return true
   end
end

Source: Lua Prime Number Checker - Stack Overflow

I don’t need a prime number checker
did you even read the question and info I talked about :sweat_smile:

I’ll test this after school
if I get it to work efficiently I’ll make this the solution

My bad read over the question, instead you could use the function and loop through it or do the following:

local function getPrimes(startNumber, endNumber)
   local primes = {}

   for i = startNumber, endNumber do
      if isPrime(i) then
         table.insert(primes, i)
      end
   end

   return primes
end

Else you could use Prime values of quadratic polynomials basically it is following function: image , this one has some downsides as it yields prime numbers for image

local function getPrimes()
   local primes = {}
   
   for n = 1,40 do
      table.insert(primes, (n^2 - n + 41)
   end
end

I made a function that finds the first n number of primes:

function IsPrime(Num)
	local Factors = {}
	for i = 1, Num, 1 do
		local PossibleFactor = Num/i
		if PossibleFactor % 1 == 0 then
			table.insert(Factors, PossibleFactor)
		end
	end
	if #Factors == 2 then
		return Num
	end
end

function FindPrimes(Amount)
	local Num = 0
	local Primes = {}
	repeat
		Num += 1
		if IsPrime(Num) ~= nil then
			table.insert(Primes, IsPrime(Num))
		end
	until #Primes == Amount
	print(Primes)
end

FindPrimes(11) -- Finds the first 11 primes

this obv won’t work
let’s say the min is 1 and max is 10
default count is 1
I would only be 1-10 and the first 10 prime numbers exceed that obv

as for the second one I don’t want it to be limited

yea but my question was initially, is it possible to be more efficient then a loop for this function

making one with a loop is super easy
but is inefficient