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?
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.
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.
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)
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: , this one has some downsides as it yields prime numbers for
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