SPOJ: GCD2

Problem Link http://www.spoj.com/problems/GCD2/ Problem Description In this problem, we need to find greatest common divisor(GCD) of two numbers. If there are two numbers, say A and B, then the constraints are : 1. 0<=A<=40000(can be stored in integer) 2. A<=B<=10^250 (can not be stored in integer) Concepts Used Recursion and Maths Code #include <bits/stdc++.h> using […]

Continue reading


SPOJ: TDPRIMES – Printing some primes

Problem Link http://www.spoj.com/problems/TDPRIMES/ Problem Description In this problem,we need to print 1st,101st,201st…….primes less than 10^8. Concepts Used This problem is based on prime sieve(Sieve of Eratosthenes).. Code #include<stdio.h> #include<vector> /*To check whether a number i is prime or not,we need to check a[i/2] or a[i>>1] whether it is true or false*/ #define isprime(i) (a[i>>1]) /*number […]

Continue reading


SPOJ: CPRIME – Prime Number Theorem

Problem Link http://www.spoj.com/problems/CPRIME/ Problem Description In this problem,we need to find percentage error for prime number theorem ((pi(x)-lnx)/pi(x)) % where pi(x) =number of primes not greater than x. Concepts Used This problem is based on prime sieve(Sieve of Eratosthenes).. Code #include<stdio.h> #include<vector> #include<math.h> /*To check whether a number i is prime or not,we need to […]

Continue reading


SPOJ: TDKPRIME – Finding the Kth Prime

Problem Link http://www.spoj.com/problems/TDKPRIME/ Problem Description In this problem, We need to print the value of kth prime(max value of k is 5000000) for a number of test cases. Concepts Used This problem is based on prime sieve(Sieve of Eratosthenes). Code #include<stdio.h> #include<vector> /*To check whether a number i is prime or not,we need to check […]

Continue reading


SPOJ: PRIME1 – Prime Generator

Problem Link http://www.spoj.com/problems/PRIME1/ Problem Description In this problem, We need to print all the prime numbers between two given values m and n. Concepts Used This problem is based on prime sieve(Sieve of Eratosthenes). Code #include<stdio.h> void sieve(long long int,long long int,bool[],bool[]); int main() { long long int m,n; int t; /*scan number of test […]

Continue reading


SPOJ: COINS – Bytelandian gold coins

Problem Link http://www.spoj.com/problems/COINS/ Problem Description In this problem, We can exchange each coin of value n with three coins of value (n/2),(n/3),(n/4). So, we need to find maximum value we can obtain from a coin of n value. Concepts Used This is a straightforward DP problem. Code #include<bits/stdc++.h> using namespace std; // long long int […]

Continue reading