Fastest possible prime number detection without using break or return

조회 수: 6 (최근 30일)
William 2024년 2월 20일
답변: Walter Roberson 2024년 2월 21일
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)
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")
% 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;
% 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")
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

답변 (2개)

John D'Errico
John D'Errico 2024년 2월 21일
편집: John D'Errico 2024년 2월 21일
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.
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;
PrimesList = find(Pind);
Elapsed time is 3.096687 seconds.
So only 3.09 seconds to find all primes less than 1e8.
ans = 5761455
We found 5761455 primes. The first 20 primes found were:
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?
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
Walter Roberson 2024년 2월 21일
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.


Help CenterFile Exchange에서 Loops and Conditional Statements에 대해 자세히 알아보기





Community Treasure Hunt

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

Start Hunting!

Translated by