Problem Link http://www.spoj.com/problems/CUBEFR/ Problem Description In this problem,we need to find for a given number n whether it is cube free or not. If n is cube free,we need to print its position among cube free numbers. A number n is cube free if none of the divisors of n is a cube number. 1,2,3,4,5,6,7,9,10,11,12,13 […]

# C

# SPOJ: ACODE-Alphacode

Problem Link http://www.spoj.com/problems/ACODE/ Problem Description Alice and Bob send secret encoded messages to each other. The encoding scheme is: Letter ‘A’ is assigned codeword 1, ‘B’ is assigned codeword 2, and so on down to ‘Z’ being assigned 26. Note: Only capital letters are used in the input. Now, the encoded message can be decoded […]

# 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 […]

# 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 […]

# 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 […]

# 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 […]

# 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 […]

# 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 […]

# Prime Factorization(Using Prime Sieve)

Prime factorisation of a number is finding all the prime factors of a number. For example, prime factorisation of 120 can be written as: 120=2*2*2*3*5 One method for finding prime factorisation of a number is to check for each prime number(less than given number) whether it divides the given number or not. However,we can find […]

# Sieve of Eratosthenes(Prime Sieve)

Sieve of Eratosthenes is used to find all the prime numbers up to a given number N.This method is very efficient than the brute force method(Each number between 2 and N is checked to find if it has any other factors except 1 and itself). The basic concept behind Sieve of Eratosthenes is the fact […]