Asked by Xenium Adil
on 9 Apr 2019

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..

Answer by Shubham Sangle
on 10 Jul 2019

This is link of answer to similar question https://stackoverflow.com/questions/2468412/finding-a-prime-number-after-a-given-number

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.

Sign in to comment.

Answer by 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."

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
on 10 Apr 2019

>> 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
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.

Answer by Gaurav Pratap Garg
on 23 May 2019

function k = next_prime(n)

k = n+1;

while ~isprime(k)

k = k+1;

end

end

James Tursa
on 23 May 2019

This is essentially the same answer that was already posted in a comment on April 10.

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.

Answer by 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

Sign in to comment.

Answer by 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

Walter Roberson
on 22 Sep 2019

Sign in to comment.

Answer by John D'Errico
on 22 Sep 2019

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 about 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. 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.

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. Her, I'll set the seive 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.

partialsieve = primes(1000);

partialsieve(1) = [];

% finally, we can use a while loop.

flag = true;

while flag

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.

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 1 Comment

## Walter Roberson (view profile)

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/455395-next-prime-number-using-while-loops#comment_692014

Sign in to comment.