Download code

Jump to: navigation, search

Back to Sieve_of_Eratosthenes_(C_Plus_Plus)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

Sieve.cpp

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Sieve_of_Eratosthenes_(C_Plus_Plus)?oldid=15640
14 */
15 
16 #include "Sieve.h"
17 
18 std::vector<size_t> sieve_of_eratosthenes(size_t max)
19 {
20     Sieve sieve(max + 1 /* +1 to include max itself*/);
21     size_t i;
22     for(i=3; i*i <= max; i += 2)
23     {
24         if (sieve.is_composite(i))
25         {
26             continue;
27         }
28 
29         // We increment by 2*i to skip even multiples of i
30         for(size_t multiple_i=i*i; multiple_i <= max; multiple_i += 2*i)
31         {
32             sieve.set_composite(multiple_i);
33         }
34     }
35 
36     std::vector<size_t> primes;
37     primes.push_back(2);
38     for(size_t i=3; i <= max; i += 2)
39     {
40         if (!sieve.is_composite(i))
41         {
42             primes.push_back(i);
43         }
44     }
45     return primes;
46 }


hijacker
hijacker
hijacker
hijacker

Sieve.h

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Sieve_of_Eratosthenes_(C_Plus_Plus)?oldid=15640
14 */
15 
16 #ifndef _SIEVE_H_
17 #define _SIEVE_H_
18 
19 #include <vector>
20 #include <cstdlib> // size_t
21 #include <cassert>
22 
23 class Sieve
24 {
25 private:
26     std::vector<bool> sieve;
27 public:
28     Sieve(size_t size);
29     bool is_composite(size_t k);
30     void set_composite(size_t k);
31 };
32 
33 inline Sieve::Sieve(size_t size)
34   : sieve((size+1)/2)
35 { }
36 
37 inline bool Sieve::is_composite(size_t k)
38 {
39     assert(k >= 3 && (k % 2) == 1);
40     return sieve[(k-3)/2];
41 }
42 
43 inline void Sieve::set_composite(size_t k)
44 {
45     assert(k >= 3 && (k % 2) == 1);
46     sieve[(k-3)/2] = true;
47 }
48 
49 
50 std::vector<size_t> sieve_of_eratosthenes(size_t max);
51 
52 #endif // #ifndef _SIEVE_H_


hijacker
hijacker
hijacker
hijacker

test.cpp

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Sieve_of_Eratosthenes_(C_Plus_Plus)?oldid=15640
14 */
15 
16 #include <cstdlib>  // For atoi()
17 #include <ctime>    // For clock(), clock_t
18 #include <iostream>
19 #include "Sieve.h"
20 
21 using std::cout;
22 using std::endl;
23 
24 int main(int argc, char* argv[])
25 {
26     size_t max = (size_t)atoi(argv[1]);
27     int num_times = 1;
28     if (argc > 2)
29     {
30         num_times = atoi(argv[2]);
31     }
32 
33     std::vector<size_t> result;
34     clock_t start_time = clock();
35     for(int i=0; i < num_times; i++)
36     {
37         result = sieve_of_eratosthenes(max);
38     }
39     double time_in_ms = ((double)(clock() - start_time)) / CLOCKS_PER_SEC / num_times * 1000;
40     double time_per_integer_ns = time_in_ms / max * 1000000;
41 
42     cout << "Sieved over integers 1 to " << max
43          << " in " << time_in_ms << " ms (" << time_per_integer_ns << " ns per integer)"
44          << endl << endl;
45 
46     for(size_t i=0; i < result.size(); i++)
47     {
48         cout << result[i] << endl;
49     }
50 
51     return 0;
52 }


hijacker
hijacker
hijacker
hijacker