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?

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    

[Walter Roberson]

What n are you passing in? The code seems to work for me. Of course, it is going to take a long time for large n as it is not efficient code.

N = randi([2 5000])

N = 3477

next_prime(N)

ans = 3491

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 
end

[Nipun Vashistha]

Thank you very much!

The code works fine for smaller numbers for me too but when I tried to submit it on Coursera graded assignment which checked it for a large number (12345678), it didn't work well. The support team suggested that if the code is taking more than 15 seconds then it's stuck in an infinity loop.

Could you please suggest me how can I make it more efficient? I'm new to MATLAB and couldn't think of any other way to do it.

Thanks Again!

[Stephen23]

"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]

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() )

Answer 1

[Prahlad Gowtham Katte]

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.

[Walter Roberson]

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