Euclid’s Algorithm for Finding the GCD
The oldest known trivial algorithm known: int gdc (int x, int y){ int temp; while (y!=0){ temp=y; y=x%y; x=temp; } return x; } Check the Wikipedia entry to read more about it.
Category Archives: Algorithms
What’s The First Number to Have N Factors or More?
I am working on a problem where I need to find the first integer which has N or more factors, where N is provided. My approach was to pre-generate a table using the number of factors as index, and the first integer that has that number of factors or more as value. I make the […]
Counting the Factors of Large Integers
How do you count the factors of large integers? You could go from 1 up to N trying to divide it for all numbers in between, but this wouldn’t be very efficient. A better approach is to use only the prime factors of a number, as all other factors can be derived from those. In […]
Quicksort and Binary Search Algorithms in C/C++
Being able to sort and search efficiently is one of the most important and most studied aspects of computer science. In my opinion any programmer worth his salt should be able to, in a matter of 10 minutes or so, be able to write the algorithms of binary search as well as those of the […]
Testing If A Number is Prime Efficiently
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 […]
Exponentiation by Breaking into Powers of 2
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 […]
Fast Exponentiation Algorithms
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–; } […]
Integer Partition Algorithm
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 […]
Knapsack Problem Dynamic Programming Algorithm
The Knapsack problem is probably one of the most interesting and most popular in computer science, especially when we talk about dynamic programming. Here’s the description: Given a set of items, each with a weight and a value, determine which items you should pick to maximize the value while keeping the overall weight smaller than […]
The Sieve of Eratosthenes (Implemented in C)
If you like programming puzzles and challenges you’ll notice that many of them involve prime numbers in one way or another. As such it becomes handy to have a large table of prime numbers ready to go. One of the easiest yet efficient methods to generate a list of prime numbers if the Sieve of […]