Prime Number A prime number is a Positive Integer which has no Divisors other than 1 and itself. Although the number 1 used to be considered a prime, it requires special treatment in so many definitions and applications involving primes greater than or equal to 2 that it is usually placed into a class of its own. Since 2 is the only Even prime, it is also somewhat special, so the set of all primes excluding 2 is called the `` Odd Primes .'' The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (Sloane's , Hardy and Wright 1979, p. 3). Positive Integers other than 1 which are not prime are called Composite The function which gives the number of primes less than a number is denoted and is called the Prime Counting Function . The theorem giving an asymptotic form for is called the Prime Number Theorem Prime numbers can be generated by sieving processes (such as the Eratosthenes Sieve ), and Lucky Numbers , which are also generated by sieving, appear to share some interesting asymptotic properties with the primes. Many Prime Factorization Algorithms have been devised for determining the prime factors of a given Integer . They vary quite a bit in sophistication and complexity. It is very difficult to build a general-purpose algorithm for this computationally ``hard'' problem, so any additional information which is known about the number in question or its factors can often be used to save a large amount of time. The simplest method of finding factors is so-called `` | |
|