Hello Guys ,
Let's talk about the mathematics used in coding contests , like checking for prime numbers, finding prime factors , LCM , GCD ,Factorials e.t.c
In this post I will be talking about an easy method to check whether a number is prime or not . For this I will be using the famous algorithm " Sieve of Eratosthenes" invented by Eratosthenes of Alexandria.
Before moving further I would like you to know what is 'bitset' . If you are familiar with this , you can jump to the next topic .
A bitset stores bits (elements with only two possible values: 0 or 1 , i.e true or false ). It is an array of bool but each Boolean value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only, so space taken by bitset bs is less than that of bool bs[N] and vector bs(N) i.e each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char).
Due to this single bit , the operation performed on bitset is faster than that of array and vector . We can access the element of bitset just like an index of an array or vector . But there is a major difference between bitset and array .
bitset starts its indexing backward that is for 10110, 0 are at 0th and 3rd indices whereas 1 are at 1st 2nd and 4th indices.
The following code explains most of the basic member functions of bitset and there usage :
#include<iostream>
#include<bitset>
#define M 32
using namespace std;
int main()
{
// default constructor initializes with all bits 0
bitset<M> bset1;
// bset2 is initialized with bits of 20
bitset<M> bset2(20);
// bset3 is initialized with bits of specified binary string
bitset<M> bset3(string("1100"));
// cout prints exact bits representation of bitset
cout << bset1 << endl; // 00000000000000000000000000000000
cout << bset2 << endl; // 00000000000000000000000000010100
cout << bset3 << endl; // 00000000000000000000000000001100
cout << endl;
// declaring set8 with capacity of 8 bits
bitset<8> set8; // 00000000
// setting first bit (or 6th index)
set8[1] = 1; // 00000010
set8[4] = set8[1]; // 00010010
cout << set8 << endl;
// count function returns number of set bits in bitset
int numberof1 = set8.count();
// size function returns total number of bits in bitset
// so there difference will give us number of unset(0)
// bits in bitset
int numberof0 = set8.size() - numberof1;
cout << set8 << " has " << numberof1 << " ones and "
<< numberof0 << " zeros\n";
// test function return 1 if bit is set else returns 0
cout << "bool representation of " << set8 << " : ";
for (int i = 0; i < set8.size(); i++)
cout << set8.test(i) << " ";
cout << endl;
// any function returns true, if atleast 1 bit
// is set
if (!set8.any())
cout << "set8 has no bit set.\n";
if (!bset1.any())
cout << "bset1 has no bit set.\n";
// none function returns true, if none of the bit
// is set
if (!bset1.none())
cout << "bset1 has all bit set\n";
// bset.set() sets all bits
cout << set8.set() << endl;
// bset.set(pos, b) makes bset[pos] = b
cout << set8.set(4, 0) << endl;
// bset.set(pos) makes bset[pos] = 1 i.e. default
// is 1
cout << set8.set(4) << endl;
// reset function makes all bits 0
cout << set8.reset(2) << endl;
cout << set8.reset() << endl;
// flip function flips all bits i.e. 1 <-> 0
// and 0 <-> 1
cout << set8.flip(2) << endl;
cout << set8.flip() << endl;
// Converting decimal number to binary by using bitset
int num = 100;
cout << "\nDecimal number: " << num
<< " Binary equivalent: " << bitset<8>(num);
cout<<endl;
return 0;
}
Output :
00000000000000000000000000000000
00000000000000000000000000010100
00000000000000000000000000001100
00010010
00010010 has 2 ones and 6 zeros
bool representation of 00010010 : 0 1 0 0 1 0 0 0
bset1 has no bit set.
11111111
11101111
11111111
11111011
00000000
00000100
11111011
Decimal number: 100 Binary equivalent: 01100100
Now coming back to our initial discussion regarding prime numbers :
First, this Sieve algorithm sets all numbers in the range to be ‘probably prime’ but set
numbers 0 and 1 to be not prime. Then, it takes 2 as prime and crosses out all multiples
of 2 starting from 2 × 2 = 4, 6, 8, 10, . . . until the multiple is greater than N. Then it takes
the next non-crossed number 3 as a prime and crosses out all multiples of 3 starting from
3 × 3 = 9, 12, 15, . . .. Then it takes 5 and crosses out all multiples of 5 starting from 5 × 5 =
25, 30, 35, . . .. And so on . . .. After that, whatever left uncrossed within the range [0..N]
are primes. This algorithm does approximately (N× (1/2 + 1/3 + 1/5 + 1/7 + . . . + 1/last
prime in range ≤ N)) operations. The time complexity is of roughly O(N log log N).
Generating a list of primes ≤ 10K using the sieve is fast , we opt to use sieve for smaller
primes and for the larger prime numbers we use other methods which I will be discussing later .
The code is as follows:
#include <bitset>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
long long int _sieve_size;
bitset<10000010> bs; // 10^7 should be enough for most cases
vector<long long int> primes; // compact list of primes in form of vector<int>
void sieve(long long int upperbound)
{
// create list of primes in [0..upperbound]
_sieve_size = upperbound + 1; // add 1 to include upperbound
bs.set(); // set all bits to 1
bs[0] = bs[1] = 0;// except index 0 and 1
for (long long int i = 2; i <= _sieve_size; i++)
{
if (bs[i])
{
// cross out multiples of i starting from i * i!
for (long long int j = i * i; j <= _sieve_size; j += i)
{
bs[j] = 0;
}
primes.push_back((int)i);
// add this prime to the list of primes
}
}
}
bool isPrime(long long int N)
{
// a good enough deterministic prime tester
if (N <= _sieve_size) return bs[N];
// O(1) for small primes
cout<<(int)primes.size()<<endl;
for (int i = 0; i < (int)primes.size(); i++)
if (N % primes[i] == 0) return false;
return true;
// it takes longer time if N is a large prime!
}
// note: only work for N <= (last prime in vector "primes")^2
// inside int main()
int main()
{
sieve(10000000);
// can go up to 10^7 (need few seconds)
printf("%d\n", isPrime(2147483647));
// 10-digits prime
printf("%d\n", isPrime(136117223861LL));
// not a prime, 104729*1299709
//How are we checking this for number which are > 10^7 ??
//Actually we cn check upto prime numbers < (10^7)^2!!! using this method
//because to check whether a number is prime number or not , all we need to check whether
// the number has any factor less than (number)^(0.5) or not
}
Thank you.Keep Coding :)
Let's talk about the mathematics used in coding contests , like checking for prime numbers, finding prime factors , LCM , GCD ,Factorials e.t.c
In this post I will be talking about an easy method to check whether a number is prime or not . For this I will be using the famous algorithm " Sieve of Eratosthenes" invented by Eratosthenes of Alexandria.
Before moving further I would like you to know what is 'bitset' . If you are familiar with this , you can jump to the next topic .
A bitset stores bits (elements with only two possible values: 0 or 1 , i.e true or false ). It is an array of bool but each Boolean value is not stored separately instead bitset optimizes the space such that each bool takes 1 bit space only, so space taken by bitset bs is less than that of bool bs[N] and vector bs(N) i.e each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char).
Due to this single bit , the operation performed on bitset is faster than that of array and vector . We can access the element of bitset just like an index of an array or vector . But there is a major difference between bitset and array .
bitset starts its indexing backward that is for 10110, 0 are at 0th and 3rd indices whereas 1 are at 1st 2nd and 4th indices.
The following code explains most of the basic member functions of bitset and there usage :
#include<iostream>
#include<bitset>
#define M 32
using namespace std;
int main()
{
// default constructor initializes with all bits 0
bitset<M> bset1;
// bset2 is initialized with bits of 20
bitset<M> bset2(20);
// bset3 is initialized with bits of specified binary string
bitset<M> bset3(string("1100"));
// cout prints exact bits representation of bitset
cout << bset1 << endl; // 00000000000000000000000000000000
cout << bset2 << endl; // 00000000000000000000000000010100
cout << bset3 << endl; // 00000000000000000000000000001100
cout << endl;
// declaring set8 with capacity of 8 bits
bitset<8> set8; // 00000000
// setting first bit (or 6th index)
set8[1] = 1; // 00000010
set8[4] = set8[1]; // 00010010
cout << set8 << endl;
// count function returns number of set bits in bitset
int numberof1 = set8.count();
// size function returns total number of bits in bitset
// so there difference will give us number of unset(0)
// bits in bitset
int numberof0 = set8.size() - numberof1;
cout << set8 << " has " << numberof1 << " ones and "
<< numberof0 << " zeros\n";
// test function return 1 if bit is set else returns 0
cout << "bool representation of " << set8 << " : ";
for (int i = 0; i < set8.size(); i++)
cout << set8.test(i) << " ";
cout << endl;
// any function returns true, if atleast 1 bit
// is set
if (!set8.any())
cout << "set8 has no bit set.\n";
if (!bset1.any())
cout << "bset1 has no bit set.\n";
// none function returns true, if none of the bit
// is set
if (!bset1.none())
cout << "bset1 has all bit set\n";
// bset.set() sets all bits
cout << set8.set() << endl;
// bset.set(pos, b) makes bset[pos] = b
cout << set8.set(4, 0) << endl;
// bset.set(pos) makes bset[pos] = 1 i.e. default
// is 1
cout << set8.set(4) << endl;
// reset function makes all bits 0
cout << set8.reset(2) << endl;
cout << set8.reset() << endl;
// flip function flips all bits i.e. 1 <-> 0
// and 0 <-> 1
cout << set8.flip(2) << endl;
cout << set8.flip() << endl;
// Converting decimal number to binary by using bitset
int num = 100;
cout << "\nDecimal number: " << num
<< " Binary equivalent: " << bitset<8>(num);
cout<<endl;
return 0;
}
Output :
00000000000000000000000000000000
00000000000000000000000000010100
00000000000000000000000000001100
00010010
00010010 has 2 ones and 6 zeros
bool representation of 00010010 : 0 1 0 0 1 0 0 0
bset1 has no bit set.
11111111
11101111
11111111
11111011
00000000
00000100
11111011
Decimal number: 100 Binary equivalent: 01100100
Now coming back to our initial discussion regarding prime numbers :
First, this Sieve algorithm sets all numbers in the range to be ‘probably prime’ but set
numbers 0 and 1 to be not prime. Then, it takes 2 as prime and crosses out all multiples
of 2 starting from 2 × 2 = 4, 6, 8, 10, . . . until the multiple is greater than N. Then it takes
the next non-crossed number 3 as a prime and crosses out all multiples of 3 starting from
3 × 3 = 9, 12, 15, . . .. Then it takes 5 and crosses out all multiples of 5 starting from 5 × 5 =
25, 30, 35, . . .. And so on . . .. After that, whatever left uncrossed within the range [0..N]
are primes. This algorithm does approximately (N× (1/2 + 1/3 + 1/5 + 1/7 + . . . + 1/last
prime in range ≤ N)) operations. The time complexity is of roughly O(N log log N).
Generating a list of primes ≤ 10K using the sieve is fast , we opt to use sieve for smaller
primes and for the larger prime numbers we use other methods which I will be discussing later .
The code is as follows:
#include <bitset>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
long long int _sieve_size;
bitset<10000010> bs; // 10^7 should be enough for most cases
vector<long long int> primes; // compact list of primes in form of vector<int>
void sieve(long long int upperbound)
{
// create list of primes in [0..upperbound]
_sieve_size = upperbound + 1; // add 1 to include upperbound
bs.set(); // set all bits to 1
bs[0] = bs[1] = 0;// except index 0 and 1
for (long long int i = 2; i <= _sieve_size; i++)
{
if (bs[i])
{
// cross out multiples of i starting from i * i!
for (long long int j = i * i; j <= _sieve_size; j += i)
{
bs[j] = 0;
}
primes.push_back((int)i);
// add this prime to the list of primes
}
}
}
bool isPrime(long long int N)
{
// a good enough deterministic prime tester
if (N <= _sieve_size) return bs[N];
// O(1) for small primes
cout<<(int)primes.size()<<endl;
for (int i = 0; i < (int)primes.size(); i++)
if (N % primes[i] == 0) return false;
return true;
// it takes longer time if N is a large prime!
}
// note: only work for N <= (last prime in vector "primes")^2
// inside int main()
int main()
{
sieve(10000000);
// can go up to 10^7 (need few seconds)
printf("%d\n", isPrime(2147483647));
// 10-digits prime
printf("%d\n", isPrime(136117223861LL));
// not a prime, 104729*1299709
//How are we checking this for number which are > 10^7 ??
//Actually we cn check upto prime numbers < (10^7)^2!!! using this method
//because to check whether a number is prime number or not , all we need to check whether
// the number has any factor less than (number)^(0.5) or not
}
Thank you.Keep Coding :)
No comments:
Post a Comment