Number Theory

From Algorithmist
Jump to navigation Jump to search
This is a stub or unfinished. Contribute by editing me.


Number Theory is the queen of mathematics. It deals with the different properties of numbers such as integers, real numbers, fractions and other pure mathematical concepts. It includes determining the properties of prime numbers, divisibility of numbers and completing large calculations in short amounts of time. For example, an N-Queens solution can be checked for incorrectness by labeling each position (or square) of the chessboard with a number from 1 to n*n starting in the top-left corner and moving from left-to-right and top-to-bottom (or another symmetrical version of this), summing the values of the positions of the queens, and checking that value against . If they do not match, then answer is incorrect. However, if they do match then each queen is on a unique row and column, but the queens may or may not be attacking one another diagonally.

Prime Number Generation[edit]

Prime numbers are a prime example of what Number Theory is about, as they have important real-world applications (RSA is built upon the difficulty of factoring the product of two large primes). Therefore, the generation of accurate prime numbers is integral to the success of these systems.

There are a few methods for determining if a number is prime, but first a simple working definition of a prime is essential. A prime is a number that is greater than 1 and cannot be divided by anything other than 1 and itself (i.e.- 7 is prime as it has no divisors other than 1 and 7 [itself], whereas 6 is not prime as it can be divided by 1, 2, 3, and 6 [itself]). Due to this definition, we can exclude at least one group of numbers- by definition, all even numbers are divisible by 2, and are therefore not prime.

Now we can get into verifying whether a number is a prime or not. A prime, by definition, is not divisible by anything in the range , so we could check if a number is divisible by every number in that range, but that would take way more time than is necessary. This is because as we move above the square root of the number, the multiplication pairs begin to repeat, therefore we can go from to a significantly reduced search space of . Also important to note is that you can specifically ensure multiples of specific numbers are not checked, as 2 and 3 are normally considered as separate cases. This will reduce time and algorithmic complexity due to significantly fewer checks per operation. This is generally referred to as a naïve approach as it is usually the first method thought of and has minimal optimization.

This is a simple implementation in Python:

def naive(n):
    if n%2==0 or n%3==0:        # check if 'n' is a multiple of 2 or 3 (assumes you aren't checking 2 or 3 through this function)
        return False            # if it is, it's not prime
    sqrt=int(((n**.5+1)//1)-1)  # efficient square root ceiling function
    for x in range(5, sqrt, 2): # check from 5 (next prime) to sqrt, but only every other number (the odds)
        if n%x==0:              # if n is divisible by a number less than it (x) 
            return False        # then it is not prime
    return True                 # it has checked every number from [2, sqrt] and isn't divisible by any, so it is prime

This will return if it is a prime number or not every time, accurately, but this function will take forever with larger numbers.

Segmented Sieve[edit]

The Segmented Sieve is another modified version of prime generator algorithms that is mainly used when the range is too large (ex: 10^5) and the numbers can not be fit on array (ex: 10^9). The implementation of segmented sieve in c++ :