Mercurial > algorithms
view sieve_of_eratosthenes/sieve.cpp @ 9:8f82abf1b732
Sieve of Eratosthenes in C++
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Wed, 03 Jun 2015 16:02:31 -0500 |
| parents | |
| children |
line source
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4 #include <sstream>
6 void sieve( int limit, std::vector<int> &primes ) {
7 std::vector<int> nums;
8 for ( int i = 0; i <= limit; ++i )
9 nums.push_back(1);
10 nums[0] = nums[1] = 0;
13 float sq = sqrt(limit);
14 for ( int i = 2; i <= sq; ++i ) {
15 if ( nums[i] != 0 ) {
16 for ( int j = i*i; j <= limit; j += i )
17 nums[j] = 0;
18 }
19 }
21 for ( int i = 2; i <= limit; ++i )
22 if ( nums[i] != 0 )
23 primes.push_back( i );
25 }
29 int main( int argc, char **argv ) {
30 int limit;
32 std::stringstream ss(argv[1]);
33 ss >> limit;
35 std::vector<int> primes;
37 sieve( limit, primes );
39 for ( int i=0; i < primes.size(); ++i )
40 std::cout << primes[i] << std::endl;
42 }