TheAlgorithms / MATLAB-Octave

This repository contains algorithms written in MATLAB/Octave. Developing algorithms in the MATLAB environment empowers you to explore and refine ideas, and enables you test and verify your algorithm.
MIT License
364 stars 173 forks source link

Improve sieve of Eratosthenes #82

Closed MaximSmolskiy closed 3 years ago

MaximSmolskiy commented 3 years ago

Sieve of Eratosthenes is quite efficient nearly linear algorithm. But current implementation is naive quadratic brute force.

Before:

>> tic; sieveER(100); toc;
Elapsed time is 0.0519161 seconds.
>> tic; sieveER(1000); toc;
Elapsed time is 5.05789 seconds.

After:

>> tic; sieveER(100); toc;
Elapsed time is 0.00150514 seconds.
>> tic; sieveER(1000); toc;
Elapsed time is 0.00985217 seconds.
cozek commented 3 years ago

Thanks!