Category Archives: Mathematics

Finding all prime numbers

Till now I just knew only one way of finding all primes i.e. Sieve of Eratosthenes or space optimized version of the same called segmented sieve or time optimized version called Euler’s Sieve.

All of above work on same fundamentals striking out composite numbers from the beginning and what is remaining are the primes.

Recently I came across another way of finding primes the process is called Sieve of Sundaram.

  • You start with all the integers from 2 to n
  • From the above list remove all numbers which are of the form i + j + 2 * i*j

    1<= i <= j

    i + j + 2 *i * j <= N
  • What is remaining is doubled and incremented by 1 to give all the primes except 2. So basically all odd primes.

Example working:

Let us start with (n = 7) i.e. 1, 2, 3, 4, 5, 6, 7
In first step let us keep i = 1 and j = 1, 2, .. so cross out 1 + 1 + 2*1*1 (=4), 1 + 2 + 2 * 2* 1 (=6) take i = 2 then all are greater than 7 so not needed.
Remaining numbers are 1, 2, 3, 5, 7 So from Sieve of Sundaram all odd primes are:
1*2+1, 2*2+1, 3*2+1 = 3, 5, 7 add 2 and you have your result(all the primes in 1 to n).

Prim’s MST (Minimum Spanning Tree)

Given a graph with N nodes and M edges (Undirected) with positive weights. Find the minimum spanning tree. A tree with minimum overall weight edge. This is cover all nodes of the original graph if possible. You will be given a starting point S. Just in case the graph is not connected. Then you can find the MST which contains S.

 

Input Format

First line has two integers , denoting the number of nodes in the graph and , denoting the number of edges in the graph.

The next lines each consist of three space separated integers , first two integers are the two nodes between which the  edge exists, last/third integer is the weight of the edge.

The last line has an integer , denoting the starting node.

Nodes are numbered from 1 to N.

There can be multiple edges between same pair of nodes. Consider them as multiple edges.

 

Sample input:

3 3
1 2 2
1 3 3
3 2 6
1

Sample Output

5

 

Solution:

</pre>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge{
int begin;
int end;
int weight;
};
//minHeap
bool comp(const edge& a, const edge& b){
return (a.weight > b.weight);
}

void print(edge e){
cout<<e.begin<<" -> "<<e.end<<" w: "<<e.weight<<endl;
}
void prims(vector <vector <edge> > &adj, int start, int V){
vector <edge> minHeap;
int result = 0;
for(int i = 0; i < adj[start].size(); i++){
minHeap.push_back(adj[start][i]);
//print(adj[start][i]);
}
make_heap (minHeap.begin(),minHeap.end(), comp);
vector <bool> visited(V);
visited[start] = true;
while(!minHeap.empty()){
edge e = minHeap.front();
//cout<<"popped ";
//print(e);
pop_heap(minHeap.begin(), minHeap.end(),comp);
minHeap.pop_back();
if(!visited[e.end]){
visited[e.end] = true;
result += e.weight;
//cout<<"res: "<<result<<endl;
for(int i = 0; i < adj[e.end].size(); i++){
minHeap.push_back(adj[e.end][i]); push_heap(minHeap.begin(), minHeap.end(), comp);
//cout<<"push ";
//print(adj[e.end][i]);
}
}
}
cout<<result<<endl;
}

int main() {
int V, E, S;
cin>>V;
cin>>E;
vector <vector <edge> > adj(V);
for(int i = 0; i < E; i++){
int start, end, weight;
cin>>start;
cin>>end;
cin>>weight;
start--;end--;
edge e1;
e1.end = end;
e1.weight = weight;
e1.begin = start;
adj[start].push_back(e1);
edge e2;
e2.end = start;
e2.weight = weight;
e2.begin = end;
adj[end].push_back(e2);
}
cin>>S;
S--;
prims(adj,S, V);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}