I tried to write a code to find the next smallest prime number greater than any given positive integer. My code is stuck in infinity loop, how can I find where is the problem?

8 views (last 30 days)
function k = next_prime(n)
t = 2;
if isscalar(n) && fix(n) == n && n > 0
while t > 0
if isprime(t) && t > n
k = t;
return
else
t = t + 1;
end
end
end
  4 Comments
Walter Roberson
Walter Roberson on 3 Feb 2022
There is no point in testing any value 1 to n for being prime when you are using isprime() to test for prime numbers.
(There can be reason to test for them being prime if you are using a different technique to find prime numbers, one that does not involve using isprime() )

Sign in to comment.

Accepted Answer

Prahlad Gowtham Katte
Prahlad Gowtham Katte on 17 Feb 2022
Hello,
I understand that you’re trying to optimize the above function to find next smallest prime number.
For optimizing the code, instead of looping from the start you can use while loop and start from number+1.The following code is an optimized function for the same objective.
function next=nextprime(n)
flag=0;
current=n+1;
while flag==0
if (isprime(current)==1)
next=current
flag=1
else
current=current+1
end
end
end
Hope it helps.
  1 Comment
Walter Roberson
Walter Roberson on 17 Feb 2022
It is hard to measure what the most optimized code is. @Prahlad Gowtham Katte's code seems to be pretty variable in run-time, even though exactly the same amount of work is being asked for each time.
That is a bit difficult to account for... unless it has to do with the fact that with more lines, there are more opportunities for interruption, since there are some services that are only executed at the beginning of a MATLAB line of code
When I used timeit() instead of tic/toc, I was getting large bursts of delay for the version of my code that uses return(), and the version that uses break() was often taking less time. But switching the timing to tic/toc, my version with return seems to be a little faster, and my version with break seems to average slightly slower than Prahlad's version. The variability makes it difficult to determine whether the effects are real.
format long g
N = 100;
P = 1073740963;
times1 = zeros(N,1);
times2 = zeros(N,1);
times3 = zeros(N,1);
for K = 1 : N; S = tic;nextprime(P); times1(K) = toc(S); end
for K = 1 : N; S = tic;nextprime_WDR(P); times2(K) = toc(S); end
for K = 1 : N; S = tic;nextprime_WDRb(P); times3(K) = toc(S); end
%assume maximum is outlier
[~, idx] = max(times1); times1(idx) = [];
[~, idx] = max(times2); times2(idx) = [];
[~, idx] = max(times3); times3(idx) = [];
%plot
plot([times1, times2, times3]);
legend({'PGK', 'WDR', 'WDR w/break'})
[mean(times1), std(times1)]
ans = 1×2
0.0232125555555556 0.00454190163631082
[mean(times2), std(times2)]
ans = 1×2
0.0226688888888889 0.00258684514690365
[mean(times3), std(times3)]
ans = 1×2
0.0231745757575758 0.00289459827352961
function next=nextprime(n)
flag=0;
current=n+1;
while flag==0
if (isprime(current)==1)
next=current;
flag=1;
else
current=current+1;
end
end
end
function current=nextprime_WDR(n)
current=n+1;
while true
if isprime(current)
return;
end
current=current+1;
end
end
function current=nextprime_WDRb(n)
current=n+1;
while true
if isprime(current)
break;
end
current=current+1;
end
end

Sign in to comment.

More Answers (0)

Community Treasure Hunt

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

Start Hunting!