# Fastest possible prime number detection without using break or return

6 views (last 30 days)
William on 20 Feb 2024
Answered: Walter Roberson on 21 Feb 2024
So I'm trying to detect the prime numbers in a set in the quickest amount of time without using break or return (because using them in my class is discouraged for some reason and I haven't learned them yet). And I've already got a working detector that's pretty quick but I'm wondering if anyone else knows any other optimizations that could be added and how to implement them. For example, if there is a way to implement only checking numbers upto sqrt(n) without a return or break cause I couldn't figure it out. (Also can't use isprime)
clc
clear
start = 1;
finish = 100;
for numEval = start:finish
% Print the number being evaluated
fprintf("Number: %d \n", numEval)
% Print "is prime" for two because it is the only even prime and evens
% are excluded from our test
if numEval == 2
fprintf("\tIs Prime \n")
end
% Exclude evens and the number one from the set because we know they
% aren't prime (except for two)
if numEval ~= 1 && rem(numEval, 2) ~= 0
% Set the first divisor equal to two at the start of the test
divisor = 2;
% Use a while loop to find the remainder for the number divided by
% every integer from two to itself until you no longer get a
% remainder
while rem(numEval, divisor) ~= 0
divisor = divisor + 1;
end
% If the final divisor is equal to the number, we know it has no
% other factors apart from one and itself, therefore it is prime
if divisor == numEval
fprintf("\tIs Prime \n")
end
end
end
Number: 1 Number: 2
Is Prime
Number: 3
Is Prime
Number: 4 Number: 5
Is Prime
Number: 6 Number: 7
Is Prime
Number: 8 Number: 9 Number: 10 Number: 11
Is Prime
Number: 12 Number: 13
Is Prime
Number: 14 Number: 15 Number: 16 Number: 17
Is Prime
Number: 18 Number: 19
Is Prime
Number: 20 Number: 21 Number: 22 Number: 23
Is Prime
Number: 24 Number: 25 Number: 26 Number: 27 Number: 28 Number: 29
Is Prime
Number: 30 Number: 31
Is Prime
Number: 32 Number: 33 Number: 34 Number: 35 Number: 36 Number: 37
Is Prime
Number: 38 Number: 39 Number: 40 Number: 41
Is Prime
Number: 42 Number: 43
Is Prime
Number: 44 Number: 45 Number: 46 Number: 47
Is Prime
Number: 48 Number: 49 Number: 50 Number: 51 Number: 52 Number: 53
Is Prime
Number: 54 Number: 55 Number: 56 Number: 57 Number: 58 Number: 59
Is Prime
Number: 60 Number: 61
Is Prime
Number: 62 Number: 63 Number: 64 Number: 65 Number: 66 Number: 67
Is Prime
Number: 68 Number: 69 Number: 70 Number: 71
Is Prime
Number: 72 Number: 73
Is Prime
Number: 74 Number: 75 Number: 76 Number: 77 Number: 78 Number: 79
Is Prime
Number: 80 Number: 81 Number: 82 Number: 83
Is Prime
Number: 84 Number: 85 Number: 86 Number: 87 Number: 88 Number: 89
Is Prime
Number: 90 Number: 91 Number: 92 Number: 93 Number: 94 Number: 95 Number: 96 Number: 97
Is Prime
Number: 98 Number: 99 Number: 100

John D'Errico on 21 Feb 2024
Edited: John D'Errico on 21 Feb 2024
You did write working code to find primes. Well done there.
But the fastest code? Without breaks, or returns. Easy peasy. Write a sieve. I'll go all the way up to 1e8. And the code here is trivially basic. See that what I did was a classic sieve code. Pind is a boolean vector, true when the loop is done for only the primes, and false for all composites.
tic
Pmax = 1e8;
Pind = true(1,Pmax);
Pind(1) = false; % 1 is not a prime
for n = 2:Pmax/2
if Pind(n)
Pind(2*n:n:end) = false;
end
end
PrimesList = find(Pind);
toc
Elapsed time is 3.096687 seconds.
So only 3.09 seconds to find all primes less than 1e8.
numel(PrimesList)
ans = 5761455
We found 5761455 primes. The first 20 primes found were:
PrimesList(1:20)
ans = 1×20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
Did we find all of the primes less than Pmax?
numel(primes(Pmax))
ans = 5761455
Yep. I will assure you that you don't want to use the code you wrote to find that set of primes.

Walter Roberson on 21 Feb 2024
The fastest possible way of doing any computation depends upon the fine details of your CPU, and upon the fine details of how memory was allocated, and upon whatever else happens to be going on on your system at the time.
The question of the fasted possible code is essentially meaningless. If you need the fastest possible code, you should be writing in assembler.

### Categories

Find more on Loops and Conditional Statements in Help Center and File Exchange

R2023a

### Community Treasure Hunt

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

Start Hunting!