MATLAB Answers

next prime number using While loops

1,271 views (last 30 days)
Xenium Adil
Xenium Adil on 9 Apr 2019
Commented: Rik on 3 Sep 2020
We have to write a function called next_prime that takes a scalar positive integer input n. Use a while-loop to find and return k, the smallest prime number that is greater than n. we may use isprime function. plz help..

Accepted Answer

John D'Errico
John D'Errico on 22 Sep 2019
Edited: John D'Errico on 2 Apr 2020
There have now been multiple answers to this homework, all of which are fairly equivalent. (The response by Shubham Sangle has a lot of good points.) Let me offer a few ideas.
A good code to solve for the next prime would try to avoid calling isprime as much as possible, because calls to isprime are expensive. Of course, this depends on how large a number you are looking at
isprime(10000000000037)
ans =
logical
1
timeit(@() isprime(10000000000037))
ans =
0.009439529724
10000000000037 is close to as large a number you can use isprime on, working in double precision. If a single test for primality costs roughly 0.01 seconds (at least on my computer, your mileage may vary) then how long will it take to find the next prime after some number?
As it turns out, 10000000000037 is the next prime that exceeds 1e13. After that, we see primes at 10000000000051, 10000000000099, 10000000000129, 10000000000183, 10000000000259...
So out as far as 1e13, the spaces between primes seem to be running around 30 to 70, sometimes more, sometims less. That means, if you wanted to find the next prime after one of those primes, you might need to test perhaps as many as 70 numbers, or more. (However, you might get unlucky, if you find yourself at the beginning of a rather large hole between primes.)
If a single test by isprime takes 0.01 seconds out there, then your code for nextprime might take as much as one second of CPU time. That is not too bad, as long as one second is acceptable to you. Even so, there are some tricks you might employ.
The idea I will suggest here relies on the concept of k-rough numbers. Thus a rough number is one that has no small prime divisors. A k-rough number is one that has no prime divisors less than k. Some definitions will allow k as the smallest divisor, whereas I won't lose any sleep over the distinction.
A test in advance for small divisors is not a bad thing. For example, you can rule out all even numbers in your search. And you can rule out all multiples of 3, 5, 7, etc. That is, suppose I picked an arbitary large integer. What is the probability that it happens to be divisible by some small primes? (I call this pre-test a partial sieve.) Thus, 50% of the time, some large number will be divisible by 2. But 2/3 of the time (67%), it will be divisible by EITHER 2, OR 3. That means we could exclude 67% of the numbers, merely by knowing in advance if they were divisuble by EITHER 2, or by 3.
100*(1 - prod(1 - 1./[2 3]))
ans =
66.6666666666667
100*(1 - prod(1 - 1./[2 3 5 7 11 13 17 19]))
ans =
82.8975977582789
100*(1 - prod(1 - 1./primes(100)))
ans =
87.9682709525065
100*(1 - prod(1 - 1./primes(1000)))
ans =
91.9034736493157
So, if we excluded all numbers that are divisible by any small prime below 1000, then we could reduce the number of calls to isprime by almost 92%. We can carry this pretty far of course. So, if we pretest for divisibility by all primes below 1e8, the exclusion rate goes down to only roughly 97%.
100*(1 - prod(1 - 1./primes(1e8)))
ans =
96.9520278389414
That is important when a single call to isprime costs 30 minutes of CPU time. (This only happens if you are looking at numbers with many thousands of decimal digits though, using perhaps the sym version of isprime.)
As such, a decent version of nextprime might look like this:
function nextp = nextprime(N)
% solve for the next prime that comes immediately after N
% insure that N is itself an integer.
if N == ceil(N)
% then N is an integer already. We need to start looking at the NEXT
% prime number though, so we need to start our search at N+1.
N = N + 1;
else
% N was not an integer at all. So ceil will suffice to increase N
N = ceil(N);
end
% is N even? If so, then since we need ony test odd numbers, since
% even numers are not prime, then we can increment it to an odd number.
% however, just in case N was so small that the next prime would have
% been 2, special case that.
if N < 2
nextp = 2;
return
elseif rem(N,2) == 0
% we only need to look at odd numbers after this.
N = N + 1;
end
% Set up a partial sieve. Here, I'll set the sieve to check for divisibility
% by primes that do not exceed 1000. We don't need to check for divisibility
% by 2 though, since we will just step around all even numbers anyway, and
% we have already excluded the case where N was less than 2. So we never
% need to worry about the only even prime at this point.
partialsieve = primes(1000);
partialsieve(1) = [];
% finally, this is just a while loop. The test in the while becomes a no-op,
% because we break out when a prime gets hit. Use a while instead of a for
% because we have no idea how long the search will go. It does take a very long
% time before the intervening distance between two primes gets very large, so
% the while loop will terminate before long.
while true
if ~all(rem(N,partialsieve))
% no need to test this candidate
N = N + 2;
else
if isprime(N)
nextp = N;
% just break out of the loop. No need to even reset flag.
break
else
N = N + 2;
end
end
end
end
This code is actually pretty efficient, allowing us to exclude tests with isprime for 92% of the numbers we might otherwise try. In fact, it looks like it had to make only one call to isprime in this example run:
timeit(@() nextprime(1e13))
ans =
0.009934246724
I can make that claim, since that is roughly the time that MATLAB took for ONE call to isprime out there. And in this next test, there should have been only 5 calls to isprime.
timeit(@() nextprime(10000000000183))
ans =
0.047855878724
The nextprime code above is efficient, since it is MUCH faster to test for divisibility by even a rather lengthy list of integers using the rem test, then it it to make one call to isprime out there.
How long will the search for the next prime require? Luckily, the primes are scattered randomly, but it takes a seriously long time before the inter-prime stride becomes terribly large. At the same time, it can be shown this stride can be arbitrarily large if you go out far enough.
As you can see below, it generally will not take that many tests before the next prime is found, but it will help if you can avoid some of those tests with careful code.
>> max(diff(primes(1e6)))
ans =
114
>> max(diff(primes(1e7)))
ans =
154
>> max(diff(primes(1e8)))
ans =
220
>> max(diff(primes(1e9)))
ans =
282
Will this all be significant for large numbers? Yes, very much so. If you plot the maximum interprime stride, as a function of the size of the numbers we are looking at, you will find that on a plot with logged x axis, the curve should be roughly linear.
semilogx(10.^[6 7 8 9],[114 154 220 282],'-o')
grid on
I'll just fit a linear polynomial to it, as:
interprimepoly = polyfit([6 7 8 9],[114 154 220 282],1)
interprimepoly =
57 -235
This will be adequate for an extrapolation, since I don't care if it is only wildly approximate.
polyval(interprimepoly,[13, 100000])
ans =
506 5699765
As such, out in the vicinity of 1e13, we may possibly be pushed to test several hundred numbers to see if they are prime. If we can intelligently exclude perhaps 90% of those tests, then we can cut the time required by up to 90%.
Further out, looking at numbers with tens or hundreds of thousands of decimal digits, the importance of avoiding millions of calls to isprime will be quite significant.

  0 Comments

Sign in to comment.

More Answers (14)

Ajith Thomas
Ajith Thomas on 10 Jul 2019
function [k]=next_prime(n)
k=0;
while isprime(k)==0
n=n+1;
k=n;
end
end
This code also will work. Please try

  3 Comments

lagoon biswal
lagoon biswal on 31 Jul 2020
bro, can u explain what's wrong in this code
function k = next_prime(n)
k=n;
while isprime(k)==0
k=k+1;
end
end
Pratik Prasun
Pratik Prasun on 1 Aug 2020
it wont work properly if n is already a prime number since isprime(k) will return true and the while loop will never execute.
lagoon biswal
lagoon biswal on 3 Aug 2020
pratik prasun , got it bro. thanks

Sign in to comment.


Irfan Hussain
Irfan Hussain on 30 Mar 2020
function k = next_prime(n)
if n < 1 || ~isscalar(n) || n == ~fix(n)
error('error');
else
i = n + 1;
while i > n
if isprime(i)
k = i;
break;
else
i = i + 1;
end
end
end

  2 Comments

Jyotika Yadav
Jyotika Yadav on 10 May 2020
why error is coming as system could not record your grade
Stephen Cobeldick
Stephen Cobeldick on 16 May 2020
When will i ever be less than or equal to n ? The inner if is superfluous. Only one variable is required.

Sign in to comment.


Anurag Goyal
Anurag Goyal on 10 Aug 2020
function k = next_prime(n)
k=0;flag=0;
while flag~=1
k=n+1;
if isprime(k)==1
flag=1;
else
n=n+1;
end
end
end

  1 Comment

Rik
Rik on 10 Aug 2020
Thank you for posting this answer. Now I can easily cheat on my homework by handing in this code. I don't even have to bother understanding the question, or the solution.

Sign in to comment.


Shubham Sangle
Shubham Sangle on 10 Jul 2019
Answer mentioned in above link mentions:
Some other methods have been suggested and I think that they are good, but it really depends on how much you want to have to store or compute on the spot. For instance if you are looking for the next prime after a very large number, then using the Sieve of Eratosthenes might not be so great because of the number of bits you would need to store.
Alternatively, you could check all odd integers between (and including) 3 and sqrt(N) on every number odd number N greater than the input number until you find the correct number. Of course you can stop checking when you find it is composite.
If you want a different method, then I would suggest using the Miller-Rabin primality test on all odd numbers above the input number (assuming the input is > 1) until a prime is found. If you follow the list, located at the bottom of the page, of numbers a to check for the given ranges, you can significantly cut down on the number of as you need to check. Of course, you might want to check at least a few of the smaller primes (3,5,7,11 for instance) before checking with Miller-Rabin.

  1 Comment

John D'Errico
John D'Errico on 10 May 2020
For a little expansion on the ideas mentioned here...
A rough number is a number that is divisible by no small primes. A k-rough number is a number that is divisible by no prime less than k. That allows us to define the extent that a number is known to be rough. (Some definiitions would have that inequality be less than, others would say less than or equal to. The difference is not really important here.)
Rough-ness is useful because it can help you to exclude numbers from testing them using isprime, because isprime is somewhat computationally intensive. Excluding all even numbers from a test essentially allows you to exclude half the numbers from testing to see if they are prime. But then you might also like to exclude all numbers divisible by 3, then 5, 7, 11, etc.
A simple test to identify 42-rough numbers is easy to implement using gcd.
prod(primes(41))
ans =
304250263527210
log2(prod(primes(41)))
ans =
48.1122518409569
So we see the product of all primes no larger than 41 is small enough that it fits perfectly into the dynamic range of a double precision integer. And if we could exclude all numbers that have at least one prime factor no larger than 41, we would manage to exclude roughly 85% of all integers.
1 - prod(1 - 1./primes(41))
ans =
0.854906329597798
For example, is the number 1e9+1 a 41-rough number? GCD will tell us.
gcd(prod(primes(41)),1e9+1)
ans =
19019
No. It has at least one small prime factor, here we see that to be 3. It may have multiple factors of 3, but we really don't care, since we know now that 1e9+1 cannot possibly be prime.
In fact, if we consider the next 10 integers that exceed 1e9, how many are 41 rough?
gcd(prod(primes(41)),1e9 + (1:10))
ans =
19019 6 23 82 15 2 1 42 1 170
The idea is to look only for numbers that have a gcd of exactly 1 with our product of small prime, since that implies the number is not divisible by any of them.
So we immediately know that of the integers following 1e9, only 1e9+7 and 1e9+9 can possibly be prime, because only they are 41 rough.
isprime(1e9+[7 9])
ans =
1×2 logical array
1 1
In fact, they are both prime numbers. If we wanted to find more primes exceeding 1e9, we could just do:
kr41 = find(gcd(prod(primes(41)),1e9 + (1:50)) == 1)
kr41 =
7 9 13 19 21 31 33 37
isprime(1e9 + kr41)
ans =
1×8 logical array
1 1 0 0 1 0 1 0
So only 8 explicit calls to isprime were needed, and half of those tests were successful in identifying a prime number.

Sign in to comment.


Rose Potter
Rose Potter on 10 Apr 2019
I was working on that exercise too and I tried
function next_prime(n)
x=n
while isprime(x) = 0
x = n+1
end
however, Matlab returns "The expression to the left of the equals sign is not a valid target for an assignment."

  6 Comments

Show 3 older comments
Xenium Adil
Xenium Adil on 10 Apr 2019
thanks a lot...... actualy i was a little bit wrong... like this
function k=next_prime(n)
k=n;
while ~isprime(n)
k=n+1;
end
So... thnks
Stephen Cobeldick
Stephen Cobeldick on 10 Apr 2019
@Xenium Adil: your function does not work:
>> next_prime(5) % wrong
ans = 5
>> next_prime(7) % wrong
ans = 7
>> next_prime(8) % infinite loop until I press ctrl+c
>>
Your function either returns an incorrect value or goes into an infinite loop. You really need to test your code and read the comments in this thread.
Xenium Adil
Xenium Adil on 10 Apr 2019
@Stephen Cobeldick yes it was.... but then i reshaped that function according to yours.. and it worked.
function k = next_prime(k)
k = k+1;
while ~isprime(k)
k = k+1;
end
end

Sign in to comment.


Gaurav Pratap Garg
Gaurav Pratap Garg on 23 May 2019
function k = next_prime(n)
k = n+1;
while ~isprime(k)
k = k+1;
end
end

  2 Comments

James Tursa
James Tursa on 23 May 2019
This is essentially the same answer that was already posted in a comment on April 10.
Aman Gupta
Aman Gupta on 27 Jun 2019
Write a function called next_prime that takes a scalar positive integer input n. Use a while-loop to find and return k, the smallest prime number that is greater than n. Feel free to use the built-in isprime function. Here are some example runs:
SOL.
function k = next_prime(n)
t = 1; %used as break statement
while (t==1)
if isprime(n+1);
k = n+1;
t=0;
else
n = n+1;
end
end
end

Sign in to comment.


Sebastián Añazco
Sebastián Añazco on 22 Sep 2019
function k = next_prime(n)
if (n == fix(n) && n > 0) == 0
error('n must be an integer positive number');
else
t = n + 1;
while isprime(t) == 0
t = t+1;
end
k = t;
end
end

  1 Comment

Walter Roberson
Walter Roberson on 22 Sep 2019
By the way, it is more efficient to send multiple numbers to isprime(), such as isprime(t:t+something)

Sign in to comment.


Kushal Gorti
Kushal Gorti on 25 Apr 2020
function k=next_prime(n)
k=n+1;
while ~all(rem(k,2:k/2))
k=k+1;
end
end

  0 Comments

Sign in to comment.


Taif Ahmed BIpul
Taif Ahmed BIpul on 15 May 2020
function k=next_prime(n)
if isscalar(n) && n>0 && n==fix(n)
n=n+1;
while ~isprime(n)
n=n+1;
end
k=n;
else
error('put a scalar positive integer\n')
end

  0 Comments

Sign in to comment.


sayan dasgoswami
sayan dasgoswami on 16 May 2020
function k= next_prime(n)
k= n*2;
while (0<n) &&(n<k)
n=n+1;
if isprime(n) == true
k=n;
end
end
end

  3 Comments

sayan dasgoswami
sayan dasgoswami on 16 May 2020
As it was written scalar positive input hence in while statement i have written 0<n. As 0 is neigther positive nor negative, we can't include 0 as an input
John D'Errico
John D'Errico on 16 May 2020
Is this a question? Your comment about 0 as an input brings that up, but if you do try to supply 0 as an input, the code written fails to find the next prime above 0. As such, this code is not a correct solution. The code also fails to run properly when n is not an integer at all.
sayan dasgoswami
sayan dasgoswami on 17 May 2020

Sir, The question tells that the input is a 'POSITIVE scalar INTEGER'. 1. As zero is neighther positive nor negetive, then simply 0 can not be considered as an input. 2. As the input is a POSITIVE INTEGER as mentioned in the question then why should we give a NON INTEGRAL value as an input. 3. Definitely you are right about a non integral input, but nowhere in the question it is mentioned that ' If the input is not an integer then return logic 0 '

Eagerly waiting for your reply so that I can improve further.

Sign in to comment.


Lokesh Kumar Gupta
Lokesh Kumar Gupta on 17 Jun 2020
Edited: Walter Roberson on 26 Jun 2020
function k = next_prime(n)
k=n+1;
while ~isprime(n+1)
n=n+1;
k=n+1;
end

  0 Comments

Sign in to comment.


saurav Tiwari
saurav Tiwari on 26 Jun 2020
function k=next_prime(n)
k=k+1
while ~isprime(k)
k=k+1
end
end

  3 Comments

Walter Roberson
Walter Roberson on 26 Jun 2020
This does not initialize k.
Deeksha Sahu
Deeksha Sahu on 24 Jul 2020
function k = next_prime(n)
k = n+1;
while ~isprime(k)
k = k+1;
end
end

Sign in to comment.


Kunal Rathod
Kunal Rathod on 26 Aug 2020
%It took a while for me too. Here's the trick
function [k] = next_prime(n)
%Checking for the condition if the input is a scalar positive integer or not.
if ~isscalar(n) || n<1 || n ~= fix(n)
error('The input should be positive scalar integer only.');
end
% we want to test whether the number higher than the input value is prime or not.
k = n + 1;
while isprime(k) ~= 1
k = k + 1;
end

  1 Comment

Rik
Rik on 26 Aug 2020
This is better documented, but it is equivalent to the answer posted by Taif Ahmed BIpul above.
Also, why are you comparing the output of isprime to 1? It is already a logical, so you can flip it with the ~ operator.

Sign in to comment.


Hicham Satti
Hicham Satti on 31 Aug 2020
%That will run very well
function k=next_prime(n)
if ~n>0 || n~=fix(n) || ~isscalar(n)
error ('Tap a integer positif scalar argument');
else
if isprime(n+1)
k=n+1;
else
j=n+1;
while ~isprime(j)
k=j+1;
j=j+1;
end
end
end

  3 Comments

Rik
Rik on 1 Sep 2020
Why did you put in the first if part? And why do you have j in your code? It will have the exact same value as k.
And why did you post this in the first place? What does it teach? Also, as it is an answer and not a comment, I will delete all copies.
Hicham Satti
Hicham Satti on 3 Sep 2020
you can try by yourself with only the variable k and tell me if the code run well.
j is for not prime values bro. with only variable k will don't execute the right results concerning the primes and not primes values both in the same time
Rik
Rik on 3 Sep 2020
Here you go: your code, but without j. It will either run the exact same or faster (although that improvement is probably too small to measure).
function k=next_prime(n)
if ~n>0 || n~=fix(n) || ~isscalar(n)
error ('Tap a integer positif scalar argument');
else
if isprime(n+1)
k=n+1;
else
k=n+1;
while ~isprime(k)
k=k+1;
end
end
end
You are correct that j is not for primes: it isn't for variables at all. It is a good habit to avoid i and j as variables. There are enough other letters you can pick if you want a single letter variable. Avoid o and l, because they look like 0 and 1, and avoid i and j because they look like 1i and 1j.
Still my questions remain. Why the if part? And why post it at all?

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!