Leeav
|
  |
 |
| Joined: 07 Sep 2006 |
| Total Posts: 1905 |
|
|
| 29 Jan 2013 02:36 PM |
Has anyone come up with a prime-counting function on roblox yet? I created one in C++ for my Combinatorics class and it works for x values over a million but usually after that it crashes. I could adapt it to lua, but im wondering if anyone has beat me to it? The method i used was the Meissel-lehmer algorithm.
|
|
|
| Report Abuse |
|
|
| 29 Jan 2013 02:40 PM |
| I think Meelo/Level140 had one a loooong time ago. The main problem is you have to do string maths, since Lua ints switch to exponent notation very quickly. |
|
|
| Report Abuse |
|
|
| 29 Jan 2013 03:38 PM |
Generating primes is relatively hard. But the algorithms tend to nto be very difficult to implement, especially in such a well-within the integer bounds.
Checking the primality of a number is fairly trivial and occurs in O(log(n)) for n bits length of O(sqrt(n)) for number size time.
It's observable that all primes are odd. Likewise, all primes are in the form n = 6k ± 1 , k > 3. You can make this go larger, too. |
|
|
| Report Abuse |
|
|
| 29 Jan 2013 03:39 PM |
| Since you have a programming language, memoization will help considerably. |
|
|
| Report Abuse |
|
|
| 29 Jan 2013 05:38 PM |
| I beleave I have a prime number generator graphing primes using a heuristic function in binary black and white and color decimal representations. It also counts the # of times looped before a suitable number was found. Changing the heuristic functions shouldn't be too hard. Let me post it here... one moment. |
|
|
| Report Abuse |
|
|
| 29 Jan 2013 05:40 PM |
Here it is. Yes, Yes, I edited it to have some nice features when I made it.
---------------------------
--Settings local DOT_SIZE = 1 local GUI_X_SIZE = 800 local GUI_Y_SIZE = 100 local DIV_ONE = 1/3 local DIV_TWO = 2/3 local LINE_COLOR = Color3.new(0.9,0.9,0.9) local START_X_VALUE = GUI_X_SIZE* 0 local NUM_OF_ROWS = 4 --Colors local pink = Color3.new(1,0,0.5) local red = Color3.new(1,0,0) local orange = Color3.new(1,0.5,0) local yellow = Color3.new(1,1,0) local green = Color3.new(0,1,0) local blue = Color3.new(0,0,1) local violet = Color3.new(1,0.5,1) local purple = Color3.new(0.5,0.25,1) local black = Color3.new(0,0,0) --Constant Function local log10_2 = math.log10(2) local log2 = function (x) local log = math.log10 return log(x)/log10_2 end local DOT = Instance.new("Frame") DOT.Size = UDim2.new(0,DOT_SIZE,0,-DOT_SIZE) DOT.BackgroundColor3 = Color3.new() DOT.BorderSizePixel = 0 DOT.ZIndex = 2 local SCREEN = Instance.new("ScreenGui") SCREEN.Parent = game.StarterGui function isPrime(x) local floor = math.floor local sum = 0 local alpha for i = 2, floor(x^(0.5)) do alpha = 1/i sum = sum + floor(x*alpha) - floor((x-1)*alpha) end local enum = 1 + floor((-1*(1/x))*sum) if enum == 1 then return true elseif enum == 0 then return false else error("enum ~= 0 or 1! x = " .. tostring(x) .. ", and enum = " .. tostring(enum)) end end function findPrime(n) local x = n while wait() do local num = (4*(x^2))-(2*x)+41 if isPrime(num) then return num, (x+1) else x = x + 1 end end end function toBinary(x) if x == 1 or x == 0 then return x elseif x > 1 then local bits = {} local lastNum = x local num local floor = math.floor while lastNum > 0 do num = lastNum lastNum = floor(lastNum*0.5) bits[#bits+1] = num%2 end return (table.concat(bits)):reverse() else error("x is less then 2, and not 1 or 0!") end end function display(y, x, b, num, GUI) local str1 = y for i = 1, str1:len() do local bin = str1:sub(i,i) if bin == "1" then local dot = DOT:clone() dot.Position = UDim2.new(0,x*DOT_SIZE,DIV_TWO,-i*DOT_SIZE) dot.Parent = GUI end end do local dot = DOT:clone() dot.Position = UDim2.new(0,x*DOT_SIZE,DIV_ONE,0) dot.Size = UDim2.new(0,DOT_SIZE,0,-DOT_SIZE*b) dot.Parent = GUI end if x%2 == 0 then local dot = DOT:clone() dot.ZIndex = 1 dot.BackgroundColor3 = LINE_COLOR dot.Position = UDim2.new(0,x*DOT_SIZE,0,0) dot.Size = UDim2.new(0,DOT_SIZE,1,0) dot.Parent = GUI end local str2 = tostring(num) local y_size = str1:len() * (1/str2:len()) for i = 1, str2:len() do local dec = str2:sub(i,i) if dec ~= "0" then local dot = DOT:clone() dot.Position = UDim2.new(0,x*DOT_SIZE,1,-i*y_size*DOT_SIZE) dot.Size= UDim2.new(0,DOT_SIZE,0,-y_size*DOT_SIZE) dot.Parent = GUI if dec == "1" then dot.BackgroundColor3 = pink elseif dec == "2" then dot.BackgroundColor3 = red elseif dec == "3" then dot.BackgroundColor3 = orange elseif dec == "4" then dot.BackgroundColor3 = yellow elseif dec == "5" then dot.BackgroundColor3 = green elseif dec == "6" then dot.BackgroundColor3 = blue elseif dec == "7" then dot.BackgroundColor3 = violet elseif dec == "8" then dot.BackgroundColor3 = purple elseif dec == "9" then dot.BackgroundColor3 = black end end end end local last = START_X_VALUE local lastLast = START_X_VALUE local num local bin for j = 1, NUM_OF_ROWS do local GUI = Instance.new("Frame") GUI.Parent = SCREEN GUI.Size = UDim2.new(0, GUI_X_SIZE, 0, GUI_Y_SIZE) GUI.Position = UDim2.new(0.5, -GUI_X_SIZE*0.5, 0, GUI_Y_SIZE*(j-1)) GUI.BackgroundColor3 = Color3.new(1,1,1) GUI.BorderSizePixel = 0 for i = 1, math.floor(GUI_X_SIZE/DOT_SIZE) do num, last = findPrime(last) bin = toBinary(num) print("I = " ..i.. ", last = " ..last.. ", Number = " .. num .. ", Binary = " .. bin .. ".") display(bin, i, last - lastLast, num, GUI) lastLast = last end end
|
|
|
| Report Abuse |
|
|
| 29 Jan 2013 05:43 PM |
| Just edit the "FindPrime(n)" function. That is the heuristic I used. I remember editing it to return n, therefor finding every prime. I think the highest prime I found using this was about 30k. Note that you can take out some waits to make it MUCH faster, however you run the risk of freezing roblox. |
|
|
| Report Abuse |
|
|
| 29 Jan 2013 05:45 PM |
| Sorry, last post. To use this, just put it in a script and put the script somewhere runnable, and start the game. the script will handle the rest. |
|
|
| Report Abuse |
|