Last active
December 17, 2015 19:29
-
-
Save bgschiller/5660702 to your computer and use it in GitHub Desktop.
A lazily evaluated infinite list of primes, implemented in C++ but inspired by the Haskell at http://www.cs.tufts.edu/~nr/comp150fp/archive/melissa-oneill/Sieve-JFP.pdf
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "prime_iterator.h" | |
#include <vector> | |
#include <algorithm> //std::binary_search | |
//allocation and initialization of the static member variable | |
std::vector<unsigned int> PrimeIterator::prime_list{2,3}; | |
PrimeIterator::PrimeIterator() : position{0} { } | |
PrimeIterator::PrimeIterator(unsigned int pos) : position{pos} { | |
if (pos >= prime_list.size()){ | |
get_next_prime(prime_list.size() - pos); | |
} | |
} | |
bool PrimeIterator::is_prime(unsigned int x){ | |
if (x <= prime_list.back()){ | |
return std::binary_search( | |
prime_list.begin(), | |
prime_list.end(), | |
x); | |
} | |
while(prime_list.back() * prime_list.back() < x){ | |
get_next_prime(); | |
} | |
for(unsigned int possible_factor : prime_list){ | |
if (x % possible_factor == 0){ | |
return false; | |
} | |
} | |
return true; | |
} | |
unsigned int PrimeIterator::operator[](unsigned int index){ | |
while (index >= prime_list.size()){ | |
get_next_prime(index - prime_list.size() + 1); | |
} | |
return prime_list[index]; | |
} | |
void PrimeIterator::get_next_prime(unsigned int n){ | |
unsigned int largest_known_prime = prime_list.back(); | |
unsigned int candidate = largest_known_prime + 2; | |
while (n > 0){ | |
if (is_prime(candidate)){ | |
prime_list.push_back(candidate); | |
largest_known_prime = candidate; | |
candidate = largest_known_prime + 2; | |
n--; | |
} | |
else { | |
candidate += 2; | |
} | |
} | |
} | |
PrimeIterator PrimeIterator::begin(){ | |
return PrimeIterator{0}; | |
} | |
PrimeIterator PrimeIterator::end(){ | |
return PrimeIterator{prime_list.size()}; | |
} | |
PrimeIterator PrimeIterator::operator++(){//prefix | |
++position; | |
if (position >= prime_list.size()){ | |
get_next_prime(position - prime_list.size() + 1); | |
} | |
return *this; | |
} | |
PrimeIterator PrimeIterator::operator++(int){//postfix | |
PrimeIterator retval = *this; | |
++position; | |
if (position >= prime_list.size()){ | |
get_next_prime(position - prime_list.size() + 1); | |
} | |
return retval; | |
} | |
bool PrimeIterator::operator==(PrimeIterator other){ | |
return this->position == other.position; | |
} | |
bool PrimeIterator::operator!=(PrimeIterator other){ | |
return this->position != other.position; | |
} | |
unsigned int PrimeIterator::operator*(){ | |
return prime_list[position]; | |
} | |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef PRIME_ITERATOR | |
#define PRIME_ITERATOR | |
#include <vector> | |
class PrimeIterator { | |
public: | |
PrimeIterator(); | |
PrimeIterator(unsigned int pos); | |
bool is_prime(unsigned int x); | |
unsigned int operator[](unsigned int index); | |
PrimeIterator begin(); | |
PrimeIterator end(); | |
PrimeIterator operator++();//prefix | |
PrimeIterator operator++(int);//postfix | |
bool operator==(PrimeIterator other); | |
bool operator!=(PrimeIterator other); | |
unsigned int operator*(); | |
private: | |
void get_next_prime(unsigned int n=1); | |
unsigned int position; | |
static std::vector<unsigned int> prime_list; | |
}; | |
#endif |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <stdio.h> | |
#include "prime_iterator.h" | |
using namespace std; | |
int main(){ | |
PrimeIterator p; | |
cout << "the first ten primes: "; | |
for(int i=0; i<10; i++){ | |
cout << p[i] << " "; | |
} | |
cout << endl; | |
printf("101 is%s prime\n", p.is_prime(101) ? "" : " not"); | |
printf("144 is%s prime\n", p.is_prime(144) ? "" : " not"); | |
cout << "using range-based for loop\n"; | |
int i=0; | |
for(unsigned int prime: p){ | |
cout << prime << " "; | |
if (i == 100) break; | |
++i; | |
} | |
cout << endl; | |
cout << "using explicit for loop\n"; | |
i=0; | |
for(PrimeIterator q= p.begin(); q != p.end(); ++q){ | |
cout << *q << " "; | |
if (i == 100) break; | |
++i; | |
} | |
cout << endl; | |
return 0; | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
primes = 2: [x | x <- [3..], isprime x] | |
isprime x = all (\p -> x `mod` p > 0) (factorsToTry x) | |
where | |
factorsToTry x = takeWhile (\p -> p*p <= x) primes |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment