In this article, I will use the C # to compile two algorithms of the number of findings, indicating the importance of the algorithm design and the analysis of the algorithm.
The number of entries is looking for a problem, and it has always been the purpose of some mathematician pursuit. Regarding the definition and nature of the number, I will not be more narrative here, I believe everyone is about this. The search of the number of points is simple, according to the nature of the number (the number of numbers should not be used in addition to 1 and its own number of other numbers) we can start from the minimum prime number 2, until the number of small 1 than it, use these numbers Except for it, if it can be tightened, it must not be the number of prime, which is a method of judging a single pixel (this algorithm is the easiest thought, the maximum time complexity). This method can be used for all the numbers that are smaller than a given integer value, but we will find that the time consuming to use this single judgment. For example, find a number of prime numbers not more than 10, we must start from 2 to judge, to judge 9 numbers, in fact, according to the methods described later, just cycle 2 times. Therefore, the following two methods will be done based on the deletion method.
Let's take a look at the idea of deleting method:
1. Add all positive integers that are smaller than the given integer N to an array;
2. Delete can be removed by some integers;
3. The elements left in the array are the number sequences of the last needed.
For the second step, we will give two methods to achieve. Let's take a look at the algorithm:
Algorithm one:
Class Prime
{
Public static int [] primelist;
Public Static Void Findprime (INT N)
{
Intlist;
INTLIST = New int [n];
For (int P = 2; p <= n; p ) INTLIST [P-1] = P;
For (int P = 2; p { INT J = P 1; While (j <= n) { IF ((INTLIST [J-1]! = 0) && ((Intlist [J-1]% P) == 0)) INTLIST [J-1] = 0; J = J 1; } } INT i = 0; For (int P = 2; p <= n; p ) { IF (Intlist [P-1]! = 0) i = i 1; } Primelist = new int [i]; i = 0; For (int P = 2; p <= n; p ) { IF (Intlist [P-1]! = 0) { Primelist [I] = Intlist [P-1]; i = i 1; } } } } In this algorithm, the number of deleted is the number of integers of the square root from 2 to N. This algorithm is better than the number of single prime numbers described earlier, and its cycle is reduced by more than one, but this algorithm is not the ideal: 1. For example, 6 can be divided by 2, can be divided by 3, then when P = 2, 6 is deleted once; when P = 3, 6 is deleted again, although according to the algorithm rule set This will not lead to collisions (if it is 0, if it is 0, if it is 0, it will not be repeatedly deleted), but this will make the algorithm are inefficient. 2. When we have a number of sequence elements, we have also walked. The first step, let's calculate the size of the array element, the second step began to assign a value, in fact these two steps we can reduce the calculation array size, you can put it in front. 3. Elements that have been deleted, that is, those elements that are not prime numbers, can not take them to remove integers, such as 4 don't take them, because the number of 4 is definitely definitely 2, and have been in front circulation deleted. Based on the above consideration, we have received an efficient algorithm: Class primegood { Public static int [] primelist; Public Static Void Findprime (INT N) { Intlist; INT LEN = N-1; INTLIST = New int [n]; For (int P = 2; p <= n; p ) INTLIST [P-1] = P; For (int P = 2; p { IF (Intlist [P-1] == 0) Continue; INT j = p * p; While (j <= n) { IF (Intlist [J-1]! = 0) { Intlist [J-1] = 0; Len = len-1; } J = J P; } } Primelist = new int [len]; INT i = 0; For (int P = 2; p <= n; p ) { IF (Intlist [P-1]! = 0) { Primelist [I] = Intlist [P-1]; i = i 1; } } } } This algorithm thinks is exactly the same as the previous algorithm, but some content is not perfect in the above algorithm. To illustrate the efficiency difference between these two algorithms, we have compiled the following main program to compare their differences: Static void Main () { Console.writeline ("start!"); DateTime myTime5 = datetime.now; PrimeGood.FindPrime (100000); / * for (int i = 0; i <= primegood.primelist.length-1; i ) { Console.writeline (primegood.primelist [i]); } * / DateTime myTime6 = datetime.now; TimeSpan TimeAdd3 = MyTime6-MyTime5; Console.writeline (TimeAdd3.ticks); DateTime myTime1 = datetime.now; Prime.findprime (100000); DateTime myTime2 = datetime.now; TimeSpan TimeAdd = MyTime2-MyTime1; DateTime myTime3 = datetime.now; PrimeGood.FindPrime (100000); DateTime myTime4 = datetime.now; TimeSpan TimeAdd2 = myTime4-myTime3; Console.writeline; Console.writeline (TimeAdd2.ticks); } } By running this program, you can find that the difference is that this big (the previous algorithm is almost 30-60 times the back algorithm), see the figure below: In fact, the time complexity of these two algorithms is approximately: ⊙ (N1.5); ⊙ (N); It can be seen that the algorithm is implemented in the same problem, the algorithm design is a very important knowledge.
