Home › Algorithms

Number Theory

Greatest Common Divisor

Tue, 12/05/2006 - 01:05 — tekpool

Q: Find the greatest common divisor of 2 numbers a and b and also find 2 numbers x and y such that ax + by = GCD(a,b)

Sol:

Prime Numbers: Finding the first N Primes - Part 3 Prime Divisors

Thu, 11/24/2005 - 23:58 — tekpool

Q: Finding the first N Primes

In the last post we looked into making some improvements over Trivial Approaches

Prime Numbers: Finding the first N Primes - Part 2 Skipping Multiples

Thu, 11/24/2005 - 22:48 — tekpool

Q: Finding the first N primes.
In the last post, we looked into some trivial approaches. How can we make this faster?

Most of the work in problems like these (Finding matches) are spent in the core problem itself (Finding the match), in this case, Primality test. So lets look into how we can avoid this? One simple approach is to not do primality checks for even numbers

void GetPrimesSkipEven(int n)
{
	// Start from 5
	int j=3;
	// Set count to 1
	// 2 is already a prime
	int count = 1;
	while(count < n)
	{

Prime Numbers: Finding the first N Primes - Part 1 Trivial Approaches

Tue, 11/22/2005 - 08:58 — tekpool

Q: Finding whether or not a number is prime?

Sol: There are several ways to solve this problem. Lets look into some of the more trivial approaches as usual and try to improve on these as we move along.

By Definition, a prime number is a positive integer having exactly one positive divisor other than 1. Therefore the straightforward way to do this will be to check divisibility of the given number starting from 2 to the given number.

There are some easy ways to improve upon this basic approach.

Syndicate content