Lua, 876 Bytes
function I(a)a.s=a.s:gsub("(%d)(9*)$",function(n,k)return tostring(tonumber(n)+1)..("0"):rep(#k)end)end function D(a)a.s=a.s:gsub("(%d)(0*)$",function(n,k)return tostring(tonumber(n)-1)..("9"):rep(#k)end):gsub("^0+(%d)","%1")end function m(a,b)local A=K(a)local B=K(b)while V(0,B)do D(A)D(B)end return A end function M(a,b)local A=K(a)local B=K(b)while V(m(B,1),A)do A=m(A,B)end return A end function l(n)return#n.s end function p(a)local A=K(a)local i=K(2)while V(i,A)do if V(M(A,i),1)then return false end I(i)end return true end function V(b,a)A=K(a)B=K(b)if l(A)>l(B)then return true end if l(B)>l(A)then return false end for i=1,l(A)do c=A.s:sub(i,i)j=B.s:sub(i,i)if c>j then return true elseif c<j then return false end end return false end function K(n)if(type(n)=='table')then return{s=n.s}end return{s=tostring(n)}end P=K(io.read("*n"))repeat I(P)until p(P)print(P.s)
Lua, unlike some other languages, does have a Maximum Integer Size. Once a number gets larger than 232, things stop working correctly, and Lua starts trying to make estimates instead of exact values.
As such, I had to implement a new method of storing numbers, in particular, I've stored them as Base10 strings, because Lua doesn't have a size limit on Strings, other than the size of the memory.
I feel this answer is much more to the Spirit of the question, as it has to itself implement arbitrary precision integers, as well as a prime test.
Explained
-- String Math
_num = {}
_num.__index = _num
-- Increase a by one.
-- This works by grabbing ([0-9])999...$ from the string.
-- Then, increases the first digit in that match, and changes all the nines to zero.
-- "13", only the "3" is matched, and it increases to 1.
-- "19", firstly the 1 is turned to a 2, and then the 9 is changed to a 0.
-- "9" however, the 9 is the last digit matched, so it changes to "10"
function _num.inc(a)
a.str = a.str:gsub("(%d)(9*)$",function(num,nines)
return tostring(tonumber(num)+1)..("0"):rep(#nines)
end)
end
-- Decrease a by one
-- Much like inc, however, uses ([0-9])0...$ instead.
-- Decrements ([0-9]) by one and sets 0... to 9...
-- "13" only the "3" is matched, and it decreases by one.
-- "10", the "1" is matched by the ([0-9]), and the 0 is matched by the 0..., which gives 09, which is clipped to 9.
function _num.dec(a)
a.str = a.str:gsub("(%d)(0*)$",function(num,zeros)
return tostring(tonumber(num)-1)..("9"):rep(#zeros)
end) :gsub("^0+(%d)","%1")
end
-- Adds a and b
-- Makes A and B, so that the original values aren't modified.
-- B is then decremented until it hits 0, and A is incremented.
-- A is then returned.
function _num.__add(a,b)
local A = str_num(a)
local B = str_num(b)
while B > 0 do
A:inc()
B:dec()
end
return A
end
-- Subs b from a
-- Works just like Addition, yet Dec's A instead of Incs.
function _num.__sub(a,b)
local A = str_num(a)
local B = str_num(b)
while B > 0 do
A:dec()
B:dec()
end
return A
end
-- A % B
-- Makes A and B from a and b
-- Constantly subtracts B from A until A is less than B
function _num.__mod(a,b)
local A = str_num(a)
local B = str_num(b)
while A >= B do
A = A - B
end
return A
end
-- #a
-- Useful for golfiness
function _num.__len(n)
return #n.str
end
-- Primacy Testing
-- Generates A from a and i from 2.
-- Whilst i is less than A, i is incremented by one, and if A % i == 0, then it's not a prime, and we return false.
-- Once that finishes, we return true.
function _num.isprime(a)
local A = str_num(a)
local i = str_num(2)
while i < A do
if A%i < 1 then
return false
end
i:inc()
end
return true
end
-- b < a
-- A and B are generated from a and b
-- Fristly, if the length of A and B aren't equal, then that result is output.
-- Otherwise, each character is searched from left to right, the moment they are unequal, the difference is output.
-- If all the characters match, then it's equal. Return false.
function _num.__lt(b,a)
A=str_num(a)
B=str_num(b)
if #A > #B then
return true
end
if #B > #A then
return false
end
for i=1, #A.str do
As = A.str:sub(i,i)
Bs = B.str:sub(i,i)
if As > Bs then
return true
elseif As < Bs then
return false
end
end
return false
end
-- b <= a
-- Same as b < a, but returns true on equality.
function _num.__le(b,a)
A=str_num(a)
B=str_num(b)
if #A > #B then
return true
end
if #B > #A then
return false
end
for i=1, #A.str do
As = A.str:sub(i,i)
Bs = B.str:sub(i,i)
if As > Bs then
return true
elseif As < Bs then
return false
end
end
return true
end
-- Just straight up returns it's string component. Endlessly faster than the int equivalent, mostly because it never is anything _but_ the string form.
function _num.__tostring(a)
return a.str
end
-- Just set up the metatable...
function str_num(n)
if(type(n)=='table')then
return setmetatable({str = n.str}, _num)
end
return setmetatable({str = tostring(n)}, _num)
end
-- Generate a new str_num from STDIN
Prime = str_num(io.read("*n"))
-- This is handy, because it will call Prime:inc() atleast once, and stop at the next prime number it finds.
-- Basically, if it weren't for all that overhead of making the math possible, that's all this would be.
repeat
Prime:inc()
until Prime:isprime()
print(Prime)
Although the above uses Metatables, instead of just regular functions like the actual answer, which worked out smaller.
1Does it have to specifically be the next prime? Lots of prime searching algorithms for large primes only search certain types of numbers and therefore sometimes miss out primes... – FlipTack – 2017-01-29T10:34:41.090
Yes it has to be exactly the next prime @FlipTack. Not the next mersenne prime or anything. This is why I advised bruteforcing, (due to infinite resources, it would be ideal) but any algorithm is fine, as long as it finds the next prime. – P. Ktinos – 2017-01-29T10:35:40.620
Does the program have to validate that the input is actually a prime? Or can we just get the next prime after any input? – theonlygusti – 2017-01-29T13:38:08.263
@theonlygusti It doesnt have to validate inputs primality. – P. Ktinos – 2017-01-29T14:16:33.073
10I think you should add some serious test cases. – FlipTack – 2017-01-29T16:20:57.517
3"Your program MUST NOT be limited" but on the basis of the example I suspect that every single language in existence counts as limited if fit no other reason than using a finite type to address memory. – Peter Taylor – 2017-01-29T17:18:31.717
Side note: there isn't a $100,000 bounty for every new world-record prime—only a few benchmarks, like the first prime found with a million digits. See mersenne.org – Greg Martin – 2017-01-29T18:30:38.140
Weird, there's not a single Lisp answer to this question... – bright-star – 2017-01-29T19:26:19.233
How is this different from the primality test question? Any reasonable method is just going to be a fairly simple wrapper of the original or a builtin. – Post Rock Garf Hunter – 2017-01-30T02:31:25.113
How would this be tested anyway? No machines have infinite resources. – NoOneIsHere – 2017-01-30T03:00:02.013
Downvoting because I don't get the point of the challenge. Is it about finding the next prime number (trivial, and it has been done before) or manipulating large numbers in the context of prime number searching? It looks like none of the answers actually adresses this latter issue (which looks like the interestingone to me) - maybe because the question is unclear – drolex – 2017-01-30T08:48:39.340
If there were a machine with infinite processing power and memory it could instantly calculate the next prime with any program that actually works. There would no point in making programs either small or efficient any more, indeed, I suspect that in such a universe computers would be so cheap that I'd have better things to do than try to recoup the cost of one. I assume this is the case in your example, where a stick of gum may cost $100,000. I'd probably just ask a nearby computer to project all the great entertainment I missed into my mind before I notice my family have all died. – Jodrell – 2017-01-30T16:36:28.227
1
Possible duplicate of Is this number a prime?
– Post Rock Garf Hunter – 2017-01-30T16:47:03.710@WheatWizard No way. Finding the next prime is different. – mbomb007 – 2017-01-30T17:08:16.983
2@mbomb007 why? All of the answers except the builtin ones seen to just add an extra wrapper. – Post Rock Garf Hunter – 2017-01-30T17:13:13.207
So does pretty much any question tagged with [prime]. – mbomb007 – 2017-01-30T17:15:22.697
For all the "wtf there isnt any biggest prime number"-esque edits, the title obviously meant "next currently known biggest prime number so your sarcasm is not valid here :) – P. Ktinos – 2017-02-01T12:27:12.077