Sieve of Eratosthenes (SIMPLE SEIVE)
Given a number n, print all primes smaller than or equal to n. It is also given that
n is a small number.
Example:
Input : n =10
Output : 2 3 5 7
Input : n = 20
Output: 2 3 5 7 11 13 17 19
Segmented Sieve (Print Primes in a Range)
Given a range [low, high], print all primes in this range? For example, if the given
range is [10, 20], then output is 11, 13, 17, 19.
For the given length n, find all n-length Strobogrammatic numbers.
Strobogrammatic Number is a number whose numeral is rotationally
symmetric so that it appears the same when rotated 180 degrees. In other
words, Strobogrammatic Number appears the same right-side up and
upside down.
0 after 180° rotation : (0 → 0)
1 after 180° rotation : (1 → 1)
8 after 180° rotation : (8 → 8)
6 after 180° rotation : (6 → 9)
9 after 180° rotation : (9 → 6)
Examples :
Input : n = 2
Output : 88 11 96 69
Input : n = 4
Output : 8008 1001 9006 6009 8888 1881 9886 6889 8118 1111
9116 6119 8968 1961 9966 6969 8698 1691 9696 6699
Example 2: 21 and 27
For 21 and 27:
• The factors of 21 are 1, 3, 7, and 21.
• The factors of 27 are 1, 3, 9, and 27.
Here 21 and 27 have two common factors; they are 1 and 3. HCF is 3 and
they are not co-prime.
Example 2
Let's take a bigger n, say 24. Factorizing it into pairs, we get:
1×24=241×24=24
2×12=242×12=24
3×8=243×8=24
4×6=244×6=24
Now considering the numbers from 1 to 23:
• 2, 3, 4, 6, 8, 12 completely divide 24 and therefore are not coprime to it.
• 9, 10, 14, 15, 16, 18, 20, 21, 22 have a common factor with 24 which is greater than 1,
therefore these numbers are also not coprime to 24
• 1, 5, 7, 11, 13, 17, 19, 23 don't have any common factor other than 1 with 24, therefore,
are co-prime to it.
The count of co-prime numbers to 24 (listed above) is 8. Therefore:
�(�)=8ϕ(n)=8
CHINESE REMAINDER THEOREM
Input: num[] = {5, 7}, rem[] = {1, 3}
Output: 31
Explanation:
31 is the smallest number such that:
(1) When we divide it by 5, we get remainder 1.
(2) When we divide it by 7, we get remainder 3.
Input: num[] = {3, 4, 5}, rem[] = {2, 3, 1}
Output: 11
Explanation:
11 is the smallest number such that:
(1) When we divide it by 3, we get remainder 2.
(2) When we divide it by 4, we get remainder 3.
(3) When we divide it by 5, we get remainder 1.
Check if binary representation of a number is
palindrome or not
Check if the binary representation of a positive number is palindrome or not.
For example, 101, 11, 11011, 1001001 are palindromes. 100, 110, 1011 , etc., are not
palindromes.
EUCLID ALGORIHM
