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?

6 Ansichten (letzte 30 Tage)
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 Kommentare
Stephen23
Stephen23 am 3 Feb. 2022
"Could you please suggest me how can I make it more efficient? "
Search this forum for "prime number" and you wll find plenty of discussions on how to do this efficiently.
The search field is in the top right-hand corner of the page.
Walter Roberson
Walter Roberson am 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() )

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Prahlad Gowtham Katte
Prahlad Gowtham Katte am 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 Kommentar
Walter Roberson
Walter Roberson am 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

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (0)

Kategorien

Mehr zu Variables finden Sie in Help Center und File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by