Number Theory
Draft for Information Only Content Primes PrimesA prime is defined as natural number that can only be divided by 1 and itself. For examples, numbers 2, 3, 5, 7,... are primes. Prime numbers are one of the important types of numbers but there is no easy way to identify or find prime numbers. Sieve of EratosthenesThe sieve of Eratosthenes is a simple ancient algorithm developed by Eratosthenes to identify all prime numbers by eliminating all multiples of found primes in any given limit, n iteratively.
The concept of the sieve of Eratosthenes is simple but the sieve method is more complicated to be implemented.
Sieve of SundaramThe sieve of Sundaram is a simple deterministic algorithm developed by Sundaram in 1934 for determining all prime numbers except number 2 up to any given n by eliminating all number of the form i+j+2ij within the limit, the floor of (n1)/2 iteratively and then doubling and increaseing the remaining numbers by one. The two typical ideas are the elimintion of even numbers which are divisible by number 2 and all odd numbers except number 1 are expressed as an arithmetic progression. For example, numbers eliminated in n=200 with limit equals to 99.
Determined primes are
The sieving concept of sieve of Sundaram is similar to the crossing off composite numbers mechanism used in sieve of Eratosthenes. Instead of sieving the whole list of the given limit n, sieve of Sundaram only sieves the odd number of the list, and all odd numbers except number 1 are rearranged in an increasing order from one to floor of n/2.
The sieve of Sundaram is based on sieving the composite odd numbers since all even numbers are ignored. Since an odd number can be expressed as 2k+1, the odd number sequence can therefore be expressed as an ordered sequence in term of k. Let 2i+1 and 2j+1 be any two odd numbers. Therefore any composite odd number can be expressed as (2i+1)(2j+1)=2(i+j+2ij)+1. In other words, all composite number with sequence number k equal to i+j+2ij must be composite odd numbers. Since the sieving mechanism is an iterative operation to sieve all possible composite odd number in the list. The remaining sequence numbers in the list must be prime odd numbers. Sieve of AtkinThe sieve of Atkin is a simple algorithm developed by Atkin and Bernstein in 2004 to find all prime numbers by eliminating all multiples of number 2, 3, and 5, and testing iteratively with an irreducible binary quadratic equation to which the numbers of solution must be odd providing that the number is a squarefree numbers, in any given limit, n. The first part of the algorithm making use of the idea of sieve of Eratosthenes to eliminate must of the composites which are multiples of number 2, 3, and 5, in the list. The second part of the algorithm making use of the properties of the irreducible binary quadratic form of a number to test where a number is a squarefree composite or not, instead of checking the divisibility of a number.
Remaining numbers are divided into 3 groups with each number congruent to 1 modulo 4, 1 modulo 6, and 11 modulo 12. In order to have a common arithmetic progression, three sets of modulo 60 residues are {1,13,17,29,37,41,49,53}, {1,7,13,19,31,37,43,49}, and {11,23,47,59} .
©sideway ID: 140600001 Last Updated: 2014/6/6 Revision: 
Home (5) Computer Hardware (149) Software Application (187) Digitization (24) Numeric (19) Programming Web (578) CSS (SC) HTML Knowledge Base Common Color (SC) Html 401 Special (SC) OS (370) MS Windows Windows10 (SC) DeskTop (6) Knowledge Mathematics Formulas (8) Number Theory (206) Algebra (20) Trigonometry (18) Geometry (18) Calculus (67) Complex Analysis (21) Engineering Tables (8) Mechanical Mechanics (1) Rigid Bodies Statics (92) Dynamics (37) Fluid (5) Fluid Kinematics (5) Control Process Control (1) Acoustics (19) FiniteElement (2) Biology (1) Geography (1)  
Latest Updated Links

Copyright © 20002019 Sideway . All rights reserved Disclaimers last modified on 10 Feb 2019