Last active
September 17, 2015 07:04
-
-
Save PCJohn/6d518719a2634a7ab625 to your computer and use it in GitHub Desktop.
An efficient sieve to factorize numbers
This file contains 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
/* | |
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