Intro:
You accidentally corrupted the flow of time with a device you made for fun, that turned out to be a time machine. As a result, you got pushed to the far future. You realized that computing, processing power, and computers in general have been evolved by a huge amount, an infinite amount to be precise. So you grab yourself a computer with infinite memory and processing power. You have no idea how it can have infinite memory and infinite processing power, but you just accept it and return to the present.
Challenge:
You heard that the person who discovered the currently largest prime 2^74,207,281 − 1 got paid 100ドル.000. You decide to make a program that finds the next prime, since you want to get back the money you spent for the computer. You make one that takes input of a number, and finds the next prime number, either by bruteforcing or any other method.
Clarifications:
You have a hypothetical machine with infinite memory and processing power. Your program MUST NOT be limited (e.g.: C#'s int's can store from -2,147,483,648 to 2,147,483,647), well your program must be able to store, and work with any number of any size. You have infinite resources, so you shouldnt care if you would run out of memory if you allowed that.
Example I/O:
Input: The currently largest discovered prime with 22,338,618 digits.
Output: Exactly the next prime
Obviously, you dont have to prove that it works, as it would take a ton of time to compute in a physical machine. But if you moved your program to a hypothetical machine with infinite processing power / memory, it should compute instantly.
Finding the next prime and checking if a number is a prime, are two completely different things
-
1\$\begingroup\$ Does 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... \$\endgroup\$FlipTack– FlipTack2017年01月29日 10:34:41 +00:00Commented Jan 29, 2017 at 10:34
-
11\$\begingroup\$ I think you should add some serious test cases. \$\endgroup\$FlipTack– FlipTack2017年01月29日 16:20:57 +00:00Commented Jan 29, 2017 at 16:20
-
4\$\begingroup\$ "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. \$\endgroup\$Peter Taylor– Peter Taylor2017年01月29日 17:18:31 +00:00Commented Jan 29, 2017 at 17:18
-
1\$\begingroup\$ 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. \$\endgroup\$Wheat Wizard– Wheat Wizard ♦2017年01月30日 02:31:25 +00:00Commented Jan 30, 2017 at 2:31
-
2\$\begingroup\$ @mbomb007 why? All of the answers except the builtin ones seen to just add an extra wrapper. \$\endgroup\$Wheat Wizard– Wheat Wizard ♦2017年01月30日 17:13:13 +00:00Commented Jan 30, 2017 at 17:13
35 Answers 35
Mathematica, 9 bytes
NextPrime
-
\$\begingroup\$ ... Does this actually work? \$\endgroup\$wizzwizz4– wizzwizz42017年01月29日 15:40:22 +00:00Commented Jan 29, 2017 at 15:40
-
13\$\begingroup\$ Of course, Mathematica always has a builtin \$\endgroup\$JungHwan Min– JungHwan Min2017年01月29日 15:41:21 +00:00Commented Jan 29, 2017 at 15:41
-
\$\begingroup\$ @wizzwizz4, sure, Try it online! \$\endgroup\$Pavel– Pavel2017年01月29日 18:23:40 +00:00Commented Jan 29, 2017 at 18:23
-
7\$\begingroup\$ I believe this is Wilson's Theorem in disguise.
kis equal to the final result,mcontains(k-1)!^2. Since (k-1)! = -1 mod k only holds when k is prime, we have (k-1)!(k-1)! = 1 mod k, which when multiplied by k will be k itself. You calculate the square to get rid of the only exception of (k-1)! = 0 mod k for composite k, which occurs for k = 4. Correct? \$\endgroup\$orlp– orlp2017年01月29日 14:44:07 +00:00Commented Jan 29, 2017 at 14:44 -
\$\begingroup\$ Yes, that is correct. \$\endgroup\$Dennis– Dennis2017年01月29日 14:48:24 +00:00Commented Jan 29, 2017 at 14:48
-
\$\begingroup\$ This throws
RecursionError: maximum recursion depth exceeded in comparisonforf(1000)\$\endgroup\$ovs– ovs2017年01月29日 16:12:50 +00:00Commented Jan 29, 2017 at 16:12 -
8\$\begingroup\$ @ovs The question says we have infinite memory. Therefore we can assume an infinitely high recursion depth limit, and thus not worry about
RecursionError. \$\endgroup\$FlipTack– FlipTack2017年01月29日 16:15:53 +00:00Commented Jan 29, 2017 at 16:15
Regex 🐇 (PCRE2 v10.35 or later), (削除) 80 (削除ここまで) (削除) 77 (削除ここまで) 69 bytes
^(?=(?*x(x*))(?!(?*(xx+)(x+$))(?=2円*(x+)).*(?=3円4円$)1円2円*$))1円x+|\B|$
Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)
This is the first 🐇-regex I've written that can be really said to compute its result before turning it into a number of possible matches. This output method allows actually directly returning the result; before adopting this output method, it was impossible for a regex to return a value greater than the input.
The regex computes \$p-n\$, where \$n\$ is the input and \$p\$ is the next prime. To do this it takes advantage of the fact that there will always be a prime in the interval \$(n,2n]\$. Once that is complete, it outputs \$p-n+n=p\$ in the form of a number of possible matches.
^ # tail = N = input number
(?=
(?* # Non-atomic lookahead (try all options until matching)
x(x*) # 1円 = N - (P - N), for conjectured P > N
)
(?! # Negative lookahead - assert that this cannot match
(?* # Non-atomic lookahead (try all options until matching)
(xx+) # 2円 = try all numbers from 2 through N-1
(x+$) # 3円 = N - 2円; assert 2円 < N
)
(?= # Atomic lookahead (locks onto the first match)
2円*(x+) # 4円 = N % 2,円 giving 2円 instead of 0
)
.*(?=3円4円$) # tail = 3円 + 4円
1円 # tail -= 1円
2円*$ # Assert tail is divisible by 2円
)
)
1円 # tail = tail-1円 = P - N
x+ # add tail to the number of possible matches
|
\B # add abs(N-1) to the number of possible matches
|
$ # add 1 to the number of the possible matches; this gets
# us a return value of 2 for N==0, instead of 0 which we
# would have if simply adding N instead of abs(N-1)+1
Molecular lookahead (?*...) is used for convenience. It would be possible to port to flavors that don't have it, but the regex would be much longer – it would still need to emulate arithmetic in the range \$[0,2n]\$, but would need to do so within just \$[0,n/4]\$ or perhaps \$[0,n/3]\$, instead of \$[0,n]\$ as this version does.
Without returning the correct value for \0ドル\$, this would be 65 bytes.
Regex 🐘 (.NET), (削除) 79 (削除ここまで) (削除) 77 (削除ここまで) (削除) 71 (削除ここまで) 65 bytes
(?=(x|^)+)(?<1>x|^)+?(x*$)(?<!(?=4円*(?<=(?=2円4円*$)3円))(^x+)(x+x))
Returns its output as the capture count of group 1円.
# tail = N = input number
(?=(x|^)+) # 1円.captureCount = {N, if N>0, else 1}
(?<1>x|^)+? # Assert N > 0; 1円.captureCount += {N - P, if N>0, else 1}
(x*$) # 2円 = N - (N - P) = 2*N - P
(?<! # Right-to-left negative lookbehind
(?= # Atomic lookahead
4円* # tail = Z = N % 4,円 giving 4円 instead of 0
(?<= # Right-to-left atomic lookbehind
(?= # Atomic lookahead
2円4円*$ # Assert tail-2,円 that is, 3円+Z-2,円 is divisible by 4円
)
3円 # tail += 3円
)
)
(^x+) # 3円 = N - 4円; assert 4円 < N
(x+x) # 4円 = try all numbers from 2 through N-1
)
Without returning a value for \0ドル\$, this would be 61 bytes.
-
\$\begingroup\$ What do the emojis mean? \$\endgroup\$Bbrk24– Bbrk242023年04月14日 20:13:54 +00:00Commented Apr 14, 2023 at 20:13
-
\$\begingroup\$ @Bbrk24 Except for rabbit, they're animals documented to be able to count. Bee
🐝is output via number of matches, because counting that is fairly lightweight to implement in most languages (bees are small). Elephant🐘is output via capture count, because that is in a way kind of overkill (elephants are big), since in .NET a capture stack contains the contents of its captures, which is potentially much more information than just the number of captures. Rabbit🐇is output via number of ways it can match, because rabbits multiply (breed), and this output method is great at multiplying. \$\endgroup\$Deadcode– Deadcode2023年04月14日 20:32:46 +00:00Commented Apr 14, 2023 at 20:32 -
\$\begingroup\$ @Bbrk24 The reason I use emojis for those output methods is to differentiate them from output via the length of a string. Depending on the challenge, it can be a very different, or sometimes even impossible, to output via the length of a string instead of the count of something. Trivially it's impossible to output a number larger than the input without using a counting-style output, but also there are ones like totient function in ECMAScript where it's much more complicated and interesting to output via string length than some type of count. \$\endgroup\$Deadcode– Deadcode2023年04月14日 20:33:08 +00:00Commented Apr 14, 2023 at 20:33
-
\$\begingroup\$ Interesting, thanks! \$\endgroup\$Bbrk24– Bbrk242023年04月14日 20:34:07 +00:00Commented Apr 14, 2023 at 20:34
Python 2, (削除) 78 (削除ここまで) (削除) 77 (削除ここまで) (削除) 76 (削除ここまで) 74 bytes
def f(n):
while 1:
n+=1
if[i for i in range(1,n)if n%i<1]==[1]:return n
-1 byte thanks to @KritixiLithos
-1 byte thanks to @FlipTack
-2 bytes thanks to @ElPedro
-
\$\begingroup\$
n%i<1is shorter thann%i==0\$\endgroup\$user41805– user418052017年01月29日 11:39:31 +00:00Commented Jan 29, 2017 at 11:39 -
\$\begingroup\$ You don't need whitespace after that
if. \$\endgroup\$FlipTack– FlipTack2017年01月29日 11:58:36 +00:00Commented Jan 29, 2017 at 11:58 -
\$\begingroup\$ I think you mean
<1\$\endgroup\$Jonathan Allan– Jonathan Allan2017年01月29日 12:05:15 +00:00Commented Jan 29, 2017 at 12:05 -
1\$\begingroup\$ @ElPedro is right. You can change the 2 spaces in front of
n+=1andifinto tabs and save 2 bytes \$\endgroup\$user63571– user635712017年01月29日 15:44:26 +00:00Commented Jan 29, 2017 at 15:44 -
1
Jelly, 2 bytes
Æn
This implicitly takes input z and, according to the manual, generate the closest prime strictly greater than z.
Bash + coreutils, 52 bytes
for((n=1,ドルn++;`factor $n|wc -w`-2;n++)){ :;};echo $n
The documentation for bash and factor do not specify a maximum integer value they can handle (although, in practice, each implementation does have a maximum integer value). Presumably, in the GNU of the future on your infinitely large machines, bash and factor will have unlimited size integers.
-
\$\begingroup\$ Actually the docs do specify for factor that if built without gnu mp only single-precision is supported. \$\endgroup\$Dani_l– Dani_l2017年01月29日 15:44:12 +00:00Commented Jan 29, 2017 at 15:44
-
1\$\begingroup\$ @Dani_l Well, the man entry for bash only says: "Evaluation is done in fixed-width integers with no check for overflow, though division by 0 is trapped and flagged as an error." It doesn't specify the width. (As I recall, the stock implementations of bash on my machines use 64-bit signed integers, but I can't check right now.) As for factor, it will surely be updated: the OP's future computers with infinite resources will have factor compiled with gnu_up to get unlimited precision :). \$\endgroup\$Mitchell Spector– Mitchell Spector2017年01月29日 17:05:30 +00:00Commented Jan 29, 2017 at 17:05
Maxima, 10 bytes
next_prime
A function returns the smallest prime bigger than its argument.
Python with sympy, 28 bytes
import sympy
sympy.nextprime
sympy.nextprime is a function which does what it says on the tin. Works for all floats.
Python, (削除) 66 (削除ここまで) 59 bytes
-4 bytes thanks to Lynn (use -~)
-3 bytes thanks to FlipTack (use and and or, allowing ...==1 to be switched to a ...-1 condition.)
f=lambda n:sum(-~n%-~i<1for i in range(n))-1and f(n+1)or-~n
A recursive function that counts up from n until a prime is found by testing that only one number exists up to n-1 that divides it (i.e. 1). Works for all integers, raises an error for floats.
Works on 2.7.8 and 3.5.2, does not work on 3.3.3 (syntax error due to lack of space between ==1 and else)
-
\$\begingroup\$
(n+1)%(i+1)is-~n%-~i, I think. \$\endgroup\$lynn– lynn2017年01月29日 12:44:36 +00:00Commented Jan 29, 2017 at 12:44 -
\$\begingroup\$ It is, thanks... I was trying to do a shorter one using Wilson's theorem. \$\endgroup\$Jonathan Allan– Jonathan Allan2017年01月29日 12:48:40 +00:00Commented Jan 29, 2017 at 12:48
-
\$\begingroup\$ Does short circuiting
and/orwork, such asf=lambda n:sum(-~n%-~i<1for i in range(n))==1and-~n or f(n+1)? \$\endgroup\$FlipTack– FlipTack2017年01月29日 16:18:58 +00:00Commented Jan 29, 2017 at 16:18 -
\$\begingroup\$ In fact, that ^ can be golfed to
f=lambda n:sum(-~n%-~i<1for i in range(n))-1and f(n+1)or-~n\$\endgroup\$FlipTack– FlipTack2017年01月29日 16:20:18 +00:00Commented Jan 29, 2017 at 16:20 -
\$\begingroup\$ @FlipTack I originally avoided them so it could pass through zero, but it'll work - that's a three byte save! \$\endgroup\$Jonathan Allan– Jonathan Allan2017年01月30日 00:28:01 +00:00Commented Jan 30, 2017 at 0:28
Python, (削除) 114 (削除ここまで) 83 bytes
def g(b):
while 1:
b+=1
for i in range(2,b):
if b%i<1:break
else:return b
Without builtins, if there are any.
-30 by removing whitespace and -1 by changing b%i==0 to b%i<1
-
3\$\begingroup\$ This won't find the next prime if you put in
1\$\endgroup\$FlipTack– FlipTack2017年01月29日 11:07:22 +00:00Commented Jan 29, 2017 at 11:07 -
\$\begingroup\$ It now assumes that b>2 \$\endgroup\$sagiksp– sagiksp2017年01月29日 11:49:46 +00:00Commented Jan 29, 2017 at 11:49
-
\$\begingroup\$ You can't just make up your own rules... you need to follow the challenge specification. Nowhere does it say that you can assume the bounds of the input. \$\endgroup\$FlipTack– FlipTack2017年01月29日 11:56:48 +00:00Commented Jan 29, 2017 at 11:56
-
\$\begingroup\$ Even with that assumption, this fails for all even valued inputs. \$\endgroup\$FlipTack– FlipTack2017年01月29日 11:57:10 +00:00Commented Jan 29, 2017 at 11:57
-
\$\begingroup\$ I'm an idiot, i misread it. Fixed it. @FlipTack \$\endgroup\$sagiksp– sagiksp2017年01月29日 12:06:42 +00:00Commented Jan 29, 2017 at 12:06
Perl 6, 25 bytes
{first *.is-prime,$_^..*}
How it works
{ } # A lambda.
$_ ..* # Range from the lambda argument to infinity,
^ # not including the start point.
first , # Iterate the range and return the first number which
*.is-prime # is prime.
Perl 6, 32 bytes
{first {all $_ X%2..^$_},$_^..*}
With inefficient custom primality testing.
How it works
Outer structure is the same as above, but the predicate passed to first (to decide if a given number is prime), is now:
{ } # A lambda.
$_ # Lambda argument (number to be tested).
2..^$_ # Range from 2 to the argument, excluding the end-point.
X # Cartesian product of the two,
% # with the modulo operator applied to each pair.
all # Return True if all the modulo results are truthy (i.e. non-0).
Pyke, (削除) 8 (削除ここまで) 7 bytes
~p#Q>)h
4 bytes, noncompeting
(Interpreter updated since challenge posted)
~p<h
~p - primes_iterator()
< - filter(^, input() < i)
h - ^[0]
-
\$\begingroup\$ Why's the second noncompeting? I don't understand enough. \$\endgroup\$user36219– user362192017年01月29日 13:39:14 +00:00Commented Jan 29, 2017 at 13:39
-
\$\begingroup\$ @theonlygusti: Typically, the only legitimate reason to mark a submission noncompeting here (as opposed to not submitting it at all) is because you fixed a bug or added a feature in the language the program's written in, and that helped you with the challenge. (I tend to write it as "language postdates challenge" to be more clear.) \$\endgroup\$user62131– user621312017年01月29日 15:48:29 +00:00Commented Jan 29, 2017 at 15:48
-
\$\begingroup\$ @theonlygusti clarified \$\endgroup\$Blue– Blue2017年01月29日 15:58:05 +00:00Commented Jan 29, 2017 at 15:58
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.
Vyxal, 2 bytes
∆Ṗ
Here for completeness. Like answers in many other golfing langs, ∆Ṗ is simply a builtin for "next prime greater than n". It uses sympy.nextprime from Python's sympy library to do this
J, 4 bytes
4&p:
Simple built in for next prime.
05AB1E, (削除) 16 (削除ここまで) 13 bytes (Emigna @ -3 bytes)
2•7£?ÿ•o[>Dp#
2•7£?ÿ•o # Push current largest prime.
[ # # Until true..
>Dp # Increment by 1, store, check primality.
# After infinite loop, implicitly return next prime.
-
\$\begingroup\$ Wouldn't
[>Dp#work? \$\endgroup\$Emigna– Emigna2017年01月30日 16:14:03 +00:00Commented Jan 30, 2017 at 16:14 -
\$\begingroup\$ You can still cut 8 more bytes as the program should take a prime as input and output the next prime. \$\endgroup\$Emigna– Emigna2017年01月30日 17:28:42 +00:00Commented Jan 30, 2017 at 17:28
-
\$\begingroup\$ @Emigna then this question is a duplicate. \$\endgroup\$Magic Octopus Urn– Magic Octopus Urn2017年01月30日 17:34:20 +00:00Commented Jan 30, 2017 at 17:34
-
\$\begingroup\$ That is probable yes. \$\endgroup\$Emigna– Emigna2017年01月30日 17:35:33 +00:00Commented Jan 30, 2017 at 17:35
Perl, 30 bytes (29 +1 for -p):
(1x++$_)=~/^(11+?)1円+$/&&redo
Usage
Input the number after pressing return (input 12345 in example below, outputs 12347):
$ perl -pe '(1x++$_)=~/^(11+?)1円+$/&&redo'
12345
12347
How it works
- Define a string of
1's that has length++$_, where$_is initially the input value - The regex checks to see if the string of
1s is non-prime length (explained here). - If the string length is non-prime, the check is re-evaluated for the next integer (
++$_) - If the string length is prime, the implicit
whileloop exits and-pprints the value of$_ - Note: there is no need to handle the edge case
"1"of length 1 because it will never be used for values less than1, per the specification.
Java 7, (削除) 373 (削除ここまで) (削除) 343 (削除ここまで) (削除) 334 (削除ここまで) (削除) 303 (削除ここまで) 268 bytes
import java.math.*;class M{public static void main(String[]a){BigInteger n,i,o,r=new BigInteger(a[0]);for(r=r.add(o=r.ONE);;r=r.add(o)){for(n=r,i=o.add(o);i.compareTo(n)<0;n=n.mod(i).compareTo(o)<0?r.ZERO:n,i=i.add(o));if(n.compareTo(o)>0)break;}System.out.print(r);}}
-75 bytes thanks @Poke
Ungolfed:
import java.math.*;
class M{
public static void main(String[] a){
BigInteger n,
i,
o,
r = new BigInteger(a[0]);
for(r = r.add(o = r.ONE); ; r = r.add(o)){
for(n = r, i = o.add(o); i.compareTo(n) < 0; n = n.mod(i).compareTo(o)< 0
? r.ZERO
: n,
i = i.add(o));
if(n.compareTo(o) > 0){
break;
}
}
System.out.print(r);
}
}
Some example input/outputs:
7 -> 11
1609 -> 1613
104723 -> 104729
-
\$\begingroup\$ @Poke I've golfed another 31 bytes by adding
staticfor the field and methodp, but removing methodcandp's parameter. \$\endgroup\$Kevin Cruijssen– Kevin Cruijssen2017年02月01日 16:18:00 +00:00Commented Feb 1, 2017 at 16:18
05AB1E, 2 bytes
ÅN
ÅN # full program
ÅN # push smallest prime greater than...
# implicit input
# implicit output
Husk, (削除) 4 (削除ここまで) 3 bytes
Edit: -1 byte thanks to Leo
ḟṗ→
ḟ # first element that
ṗ # is a prime,
→ # counting up beginning at one greater than the input
-
\$\begingroup\$
ḟcan take a number rather than a list as second argument, and count up from that tio.run/##yygtzv7//@GO@Q93Tn/UNun///@GBgaWAA \$\endgroup\$Leo– Leo2021年02月08日 23:13:51 +00:00Commented Feb 8, 2021 at 23:13 -
\$\begingroup\$ @Leo - Thanks! I really should have read the manual... \$\endgroup\$Dominic van Essen– Dominic van Essen2021年02月08日 23:41:01 +00:00Commented Feb 8, 2021 at 23:41
Java, 176 Bytes
import java.math.*;import java.util.*;class a{public static void main(String[] args){System.out.print(new BigInteger(new Scanner(System.in).nextLine()).nextProbablePrime());}}
-
\$\begingroup\$ Welcome to the site and nice first answer! Be sure to check out our Tips for golfing in Java \$\endgroup\$2021年02月10日 17:53:47 +00:00Commented Feb 10, 2021 at 17:53
-
\$\begingroup\$ @ChartZBelatedly thanks! that was very helpful! \$\endgroup\$James Brotherhood– James Brotherhood2021年03月09日 02:03:04 +00:00Commented Mar 9, 2021 at 2:03
Vyxal, 40 bits1, 5 bytes
{›:æ¬|
Non-built-in answer, but does use a prime check built-in
Explained
{›:æ¬|
{ | # While
› # incrementing the top of the stack
:æ¬ # gives a non prime number:
# do nothing. just run the condition actually.
Vyxal, 52 bits1, 6.5 bytes
{›:KḢ3¬|
Uses KḢ3 as a prime check (len(factors(x)[1:] == 1)
Nekomata -1, 3 bytes
Ƥ$>
Explanation
Ƥ$> # Implicit input
Ƥ # Find the first prime
> # which is greater than
$ # the input integer
# Implicit output
Thunno 2, 3 bytes
μƘP
Explanation
μƘP # Implicit input
μƘ # Find the next number after the input
P # which is a prime number
# Implicit output
QBIC, 34 bytes
:{a=a+1[2,a/2|~a%b=0|b=a]]~a<b|_Xa
Based off this QBIC primality tester. Explanation:
:{a=a+1 Read 'a' from the command line, start an infinite loop
and at the start of each iteration increment 'a'
[2,a/2| FOR b = 2, b <= a/2, b++
~a%b=0| IF b cleanly divides a, we're no prime
b=a]] so, break out of the FOR loop ( ]] = End if, NEXT )
~a<b| If the FOR loop completed without breaking
_Xa then quit, printing the currently tested (prime) number
The second IF and the DO-loop are implicitly closed by QBIC.
JavaScript (ES7), 61 bytes
a=>{for(;a++;){for(c=0,b=2;b<a;b++)a%b||c++;if(!c)return a;}}
Usage
f=a=>{for(;a++;){for(c=0,b=2;b<a;b++)a%b||c++;if(!c)return a;}}
f(2)
Output
3
-
\$\begingroup\$ Nice, but I don't think this will work, as JavaScript itself (not the computer) will lose precision after just 2^53. \$\endgroup\$ETHproductions– ETHproductions2017年01月29日 13:24:17 +00:00Commented Jan 29, 2017 at 13:24
-
\$\begingroup\$ You're right, but I don't think that limit can be avoided, even if we split the number up in portions of 32 bits in an array, because eventually, the number needs to be processed as a whole. If you do have an idea on how to solve this, please let me know. \$\endgroup\$Luke– Luke2017年01月29日 13:40:01 +00:00Commented Jan 29, 2017 at 13:40
-
1\$\begingroup\$ There are JS libraries for arbitrary-precision math--I even built one at some point--so I'm certain it's possible. I'll have a go the next time I'm at my computer \$\endgroup\$ETHproductions– ETHproductions2017年01月29日 14:22:39 +00:00Commented Jan 29, 2017 at 14:22
-
\$\begingroup\$ I did some googling, and it seems interesting. I'll have a shot at it too. \$\endgroup\$Luke– Luke2017年01月29日 16:00:07 +00:00Commented Jan 29, 2017 at 16:00
MATL, 3 bytes
_Yq
The function Yq returns the next prime of the absolute value of the input if the input is negative so we implicitly grab the input, negate it (_) and find the next prime using Yq.
Haskell, (削除) 42 (削除ここまで) (削除) 46 (削除ここまで) 43 bytes
f n=[i|i<-[n..],all((>0).rem i)[2..i-1]]!!1
the usual code for brute force.
Of course this finds the next smallest prime number after n. There is no biggest prime.
Works for n> 0.
edit: Assumes n is prime. Thanks to @Laikoni's advice in the comments.
-
\$\begingroup\$ You can save a byte by replacing
head[...]with[...]!!0. However I think one can assume thatnis prime, so you can use[n..]instead of[n+1..]and then take the second element with[...]!!1. \$\endgroup\$Laikoni– Laikoni2017年01月29日 18:21:55 +00:00Commented Jan 29, 2017 at 18:21