How can i add a prime counting function to this?

2 views (last 30 days)
function [ p, c ] = sieve( N )
% Sieve Of Erastothenes Test - [ p, c ] = sieve( 100 )
% The Sieve of Erastothenes is an ancient algorithm for finding prime numbers.
% For example, to find all prime numbers less than 100, list the whole numbers from 1 to 100, then
% remove multiples of 2 , then multiples of 3, then multiples of the next prime number, 5, and so
% on up to multiples of 7 (deleting multiples of prime numbers larger than 100 is unnecessary).
%%Prime number sorter (p)
p = ( 1 : 2 : N ); % Holds the prime numbers generated
% p = 1 3 5 7 9 ... N (Halves numbers required to find
% primes) ie, remove all even numbers but 2
q = length(p); % Auto expand vector from N
p(1) = 2; % p = 2 3 5 7 9 ... N
% Optimised to find primes by factor not exceeding
% root N
for i = 3 : 2 : sqrt(N)
if p( (i + 1)/2 )
p( ( (i.^2 + 1)/2) : i : q ) = 0;
end
end
p = p( p > 0 ); % Omit zeroes in final prime list
%%Prime counting function (c)
L = logical(p);
c = cumsum(L);
end
How would i go about adding a prime counter, i.e. ?(1) = 0, ?(2) = 1, ?(3) = 2, ?(4) = 2, ?(5) = 3 and so on. My issue is i have optimised the code by removing all even numbers but 2 and removing the zeroes at the end but for the counting function i require all the 1x100 numbers to convert into a logical array and add them cumulatively to generate the correct result. My arrays output at 1x25 with the zeroes and even numbers omitted.
My main idea was to add them back in just for the prime counter, but I have been unsuccessful so far.

Accepted Answer

James Tursa
James Tursa on 18 Nov 2016
n = zeros(1,N);
n(p) = 1;
c = cumsum(n);

More Answers (0)

Products

Community Treasure Hunt

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

Start Hunting!