sieve E R Algorithm
The Sieve of Eratosthenes (E R Algorithm) is an ancient and efficient technique for finding all prime numbers up to a specified integer. It was devised by the Greek mathematician Eratosthenes around 240 BC and is named in his honor. The algorithm systematically eliminates the multiples of each prime number, starting from the smallest prime, 2, and continuing up to the square root of the desired range. As it progresses, it leaves behind only the prime numbers, which are the numbers that have no divisors other than 1 and themselves.
The algorithm starts with the creation of a list of integers from 2 to the desired maximum number. It then iterates through the list, marking each non-prime number as it encounters it. For example, it begins with the first prime number, 2, marking all its multiples (excluding 2 itself) as non-prime. Then, it moves to the next unmarked number, which is 3, and marks all its multiples as non-prime. This process is repeated for each successive unmarked number until the algorithm reaches the end of the list. By the end of the procedure, all the unmarked numbers are identified as prime numbers, as they have not been marked as multiples of any smaller number. The Sieve of Eratosthenes is particularly effective for finding prime numbers in a relatively small range and is still widely used today for its simplicity and efficiency.
% sieveEr: returns a vector with prime numbers from 2 up to N
% assumes: N >= 2
function y = sieveER(N)
% precondition
assert(N >= 2,"N must be >= 2")
tmp = 2:1:N; % all numbers from 2 up to N
y = []; % the answer
% labels all composite number with 0
for i = 1 : 1 : length(tmp)
for j = i+1 : 1 : length(tmp)
if (mod(tmp(j),tmp(i)) == 0)
tmp(j) = 0;
endif
endfor
endfor
% fills up all prime numbers in vector y
for i = 1 : 1 : length(tmp)
if (tmp(i) ~= 0)
y = [y tmp(i)];
endif
endfor
endfunction
