Skip to content

Instantly share code, notes, and snippets.

@PCJohn
Last active September 17, 2015 07:04
Show Gist options
  • Save PCJohn/6d518719a2634a7ab625 to your computer and use it in GitHub Desktop.
Save PCJohn/6d518719a2634a7ab625 to your computer and use it in GitHub Desktop.
An efficient sieve to factorize numbers
/*
This is memory saving sieve that efficiently factorizes integers below an upper limit.
It generates a structure that stores the smallest prime factor of all numbers below the limit.
Given a number, it divides it by the smallest prime factor and adds the factor to the list of factors. This is repeated till the number is reduced to 1.
Bitwise operations are used to save memory while storing the sieve encoded in a list of integers.
Author: Prithvijit Chakrabarty (prithvichakra@gmail.com)
*/
#include <vector>
#include <algorithm>
#include <tuple>
#include <iostream>
#include <math.h>
#define LLI long long int
using namespace std;
class Sieve{
long * bits;
int block = sizeof(long);
int len;
public:
Sieve(int size){
len = size/block;
bits = new long[len];
for(int i = 0; i < len; i++) bits[i] = 0;
}
void set(int pos){
bits[pos/block] |= (1 << pos%block);
}
void clear(int pos){
bits[pos/block] &= ~(1 << pos%block);
}
void flip(int pos){
bits[pos/block] ^= (1 << pos%block);
}
bool is_set(int pos){
return (bits[pos/block] >> pos%block) & 1;
}
void clear(){
for(int i = 0; i < len; i++)
bits[i] = 0;
}
void print(){
for(int i = 0; i < len; i++)
cout<<bits[i]<<" ";
cout<<endl;
}
};
//Sieve from 0 to N
long * filter(long N){
long * d_list = new long[N];
Sieve s(N);
int k = 2;
long sn = N;
while(k < sn){
for(int i = k; i < sn; i += k){
if(!s.is_set(i))
d_list[i] = k;
s.set(i);
}
while(s.is_set(k)) k++;
}
s.print();
for(int i = 0; i < sn; i++)
cout<<d_list[i]<<" ";
cout<<endl;
return d_list;
}
//Find factors given the d_list
void factor(long * d_list, long n){
long div = d_list[n];
cout<<div<<endl;
while(n%div == 0) n /= div;
if(n != 1) factor(d_list, n);
}
int main(){
long N, k, * d_list;
cout<<"Enter the number: ";
cin>>N;
d_list = filter(N); //N is the upper limit: Generate the sieve up to N
cout<<"Enter a number to factor: ";
cin>>k;
factor(d_list, k);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment