For any given number (also vpi numbers), find the next prime number in the sequence of primes.
This is actually a tool in my vpi toolbox, but it works quite nicely on any number. As such, I decided it would make sense to submit the function also separately.
tic,nextprime(1000000000),toc
ans =
1000000007
Elapsed time is 0.006276 seconds.
A partial sieve scheme is used to avoid testing the primality of too many numbers. This makes it more efficient.
You can use it on lists of numbers too.
nextprime(1000:100:2000)
ans =
1009 1103 1201 1301 1409 1511 1601 1709 1801 1901 2003
You can search in either direction, above or below the starting point too.
nextprime(43420000,'above')
ans =
43420007
nextprime(43420000,'below')
ans =
43419977
The limit for nextprime when applied to double precision numbers is now 2^46. Thus you cannot find the next prime above 2^46, unless you are working with vpi numbers.
>> nextprime(2^47)
??? Error using ==> nextprime at 89
The maximum value of N (for numeric input) allowed is 2^46.
Instead, apply nextprime to any integer or set thereof as vpi numbers. This works perfectly, but you will need to install my vpi toolbox.
>> nextprime(vpi(2).^[12;47;53;86])
ans =
4099
140737488355333
9007199254740997
77371252455336267181195291
1.3 | Modification to allow inputs up to 2^46 as numeric. Also did some minor cleanup, better error messages. |
John D'Errico (view profile)
The new release that I just submitted works up to 2^46. Beyond that, vpi numbers will still work, as they have always done.
John D'Errico (view profile)
I do appreciate the review by Dr. Feldman. However, it shows a few basic misunderstandings of MATLAB. They are logical mistakes, but they reflect the point of view of someone who still thinks they are using perhaps C or JAVA or FORTRAN or PYTHON, pick your favorite language other than MATLAB.
To start with, he suggests that this code should use integers, to make it faster. The first problem (a truly fundamental one) with that suggestion is that support for operations between integers is limited in matlab. For example, in R7007b of MATLAB (not all users use the latest release, so it makes sense to do this test in a slightly older release anyway)
>> N = int64(101);
>> P = int64(23);
>> mod(N,P)
??? Undefined function or method 'mod' for input arguments of type 'int64'.
>> N = int64(101);
>> P = int64(23);
>> N*P
??? Undefined function or method 'mtimes' for input arguments of type 'int64'.
See that even the most trivial operations are not supported for int64. Likewise, uint64 is also lacking in support for these operations in this release.
>> P = uint64(23);
>> N = uint64(101);
>> mod(N,P)
??? Undefined function or method 'mod' for input arguments of type 'uint64'.
So it might be a good idea to suggest use of integers. That might possibly have been a good suggestion were we writing in one of those other languages rather than MATLAB. But we are using MATLAB here. Dr. Feldman's suggestion is a practical impossibility when arithmetic for that variable type does not exist. While I admit that that support is present for the INT32 variable type:
>> N = int32(101);
>> P = int32(23);
>> N*P
ans =
2323
>> mod(N,P)
ans =
9
Does it even speed things up? Use of int32 instead of double would be a tremendously silly thing to do, since int32 operations are not even faster than operations on doubles! In fact, use of int32 would slow down this code!
>> N = int32(1:10000);
>> P = int32(23);
>> timeit(@() mod(N,P))
ans =
0.0036231
>> N = double(1:10000);
>> P = double(23);
>> timeit(@() mod(N,P))
ans =
0.0026903
In fact, arithmetic using doubles is FASTER than int32 arithmetic. int64 or uint64 arithmetic is not even defined in the target release, so the speed is incomparable there. ;-)
NEXTPRIME does work for my vpi class, in fact, it was originally designed for those tools. However, they are slower to use than the same direct operations on double variables. So there is no reason to force all operations into the vpi class. Worse, this would restrict the utility of this function, forcing the user to have my vpi toolbox installed even to do something as trivial as finding the next prime number above 20. The reason I posted this submission separately from my vpi toolbox is because it has a broader range of utility than for just those people who would work with truly large integers.
Finally, the author suggests that NEXTPRIME should support doubles beyond 2^32. The main problem here is with MATLAB again.
>> isprime(2^32+1)
??? Error using ==> isprime at 22
The maximum value of X allowed is 2^32.
The isprime function does not work beyond 2^32, and nextprime uses isprime to make the final determination of whether a candidate number is prime, having weeded out most alternatives with a partial number sieve first. So this operation will fail. One solution here is to convert to my vpi class if the user supplies a number as large or larger than 2^32, testing first to see if the vpi tools are installed. A different solution would be to replace the call to isprime with a custom isprime call. I'll consider these alternatives as options.
Phillip M. Feldman (view profile)
This code would be more efficient if all values were stored as integers, and all operations were performed on integers. There's no reason to use floating point. Also, the limitation that numbers cannot be larger than 2^32 should be removed. Otherwise, very nice.
Krishna Prasad (view profile)
Jos (10584) (view profile)
This is a nice, well written snippet, that prime-addicts will surely appreciate.