We have already seen that one of the easiest and most efficient ways to generate a list of prime numbers is via the Sieve of Eratosthenes. What if we just need to test if a specific number is prime, though? The Naive Algorithm Optimized Say we want to test whether the number N is prime […]
I am exploring different algorithms to carry out exponentiation lately, and today I found another interesting one. The idea is to break the exponent into powers of 2, and then to pre-compute those powers using the base you are elevating. For example, suppose you want to elevate 11 to the power of 130. The naive […]
If you have been programming for a while you probably already used the mod operator a lot. Same here. What I hadn’t done was to explore the world of modular arithmetic, and it turns out it’s quite interesting and useful (e.g., cryptography). First of all let’s talk about the mod, or modulus, operator itself. The […]
Exponentiation is a very common part of mathematics, and it’s involved in many programming puzzles. If you don’t have a function already implemented for you, a simple algorithm to compute a^b (a to the power of b) would be: int expo(int a, int b){ int result = 1; while (b>0){ result *= a; b–; } […]
Here’s the description of the Problem 7: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number? In order to find the solution I wrote a simple function to test whether a number n is […]
What does the following program print? (The answer might also be that is doesn’t print anything due to compilation or run-time error). #include <stdio.h> int main(){ if("Hello World" == "Hello World"){ printf("Yes ","No "); } printf(10+"Hello World"-4); return 0; } The answer to this puzzle along with puzzle #2 can be found here.
Problem 6 has the following description: The sum of the squares of the first ten natural numbers is, 12 + 22 + … + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + … + 10)2 = 552 = 3025 Hence the difference between the […]
Huffman Coding (link to Wikipedia) is a compression algorithm used for loss-less data compression. Here’s the basic idea: each ASCII character is usually represented with 8 bits, but if we had a text filed composed of only the lowercase a-z letters we could represent each character with only 5 bits (i.e., 2^5 = 32, which […]
Problem 5 was relatively easier than the ones we saw so far. Here’s the description: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? […]
The partition of an integer is a way of writing it as a sum of positive integers. For example, the partitions of the number 5 are: 5 4+1 3+2 2+2+1 2+1+1+1 1+1+1+1+1 Notice that changing the order of the summands will not create a different partition. Now how do we find the number of different […]