Skip to content

Instantly share code, notes, and snippets.

@bgschiller
Last active December 17, 2015 19:29
Show Gist options
  • Save bgschiller/5660702 to your computer and use it in GitHub Desktop.
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
#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];
}
#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
#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;
}
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