Algorithm analysis: use screening method to seek quality
Author: cywater2000
Date: 2005-4-5
Source: http://blog.9cbs.net/cywater2000/
One. cause:
I have seen reports on the "Screening Signs" in the blog of a netizen in 9CBS very early. Since there is no specific study at the time, it did not understand the code. I feel some incredible!
...
A few days ago, I had the opportunity to learn related knowledge in a certain class, so I took it out.
Before you talk, you can take a look at the following post:
http://www.math.utah.edu/classes/216/assignment-07.html
Do you think some magical? If you just use it, there is not much better. But the so-called "knowing it, knowing it," Let's take a look at how the algorithm is coming.
two. Algorithm Description
We first set the array of intensive integers 0 to n as Sieve [N 1], and the algorithm is obtained by "step-by-step refine" method:
[Theorem 1] If the number of lots of the number of rats p is removed from Sieve, and the p * p> n, then sieve = primes (2 ... n). Where: Primes (2..n) represents all the number of prime matters between 2..n.
Therefore, the framework of the algorithm should be:
//
P = 3; // (P = 2 is not considered because the even number starts to delete)
While (p * p <= n)
{
Delete P in the Sivev;
P = next prime number;
}
/ / The number left at this time is the number of psi.
//
So problem 1: What is the multiple of P?
Since P is a magnet, P is definitely odd, so: odd number 2 = odd;
Therefore, the multiple of P can be expressed as:
... p * (p-4), p * (p-2), p * p, p * (p 2), p * (p 4) ...
"The multiple of all the numbers of small numbers is deleted from Sieve", so only consider:
P * p, p * (p 2), p * (p 4) ...
//
// "Delete the multiple of P from SiveV;"
T = p * p;
s = 2 * p;
While (t <= n)
{
Delete Too from Sieve;
T = T S;
}
//
Question 2: How to get the next number?
[Theorem 2] Let P` is the minimum element greater than P in Sieve, then P` is the next number.
//
// "P = next prime number;"
P = P 1;
While (P is not in Sieve) P = P 1;
//
Last question 3: Will the algorithm terminate? That is, is it possible to find a number in P and P * P?
[Theorem 3] The number P, and there is at least one of the numbers between P and P * P.
Finally, according to the above algorithm, we use a simple C program to describe:
/ ************************************************** ***********
* Number of requirements for improved THE SIEVE OF ERATHENES (Elavonus screening)
* Cywater2000
* 2005-4-5
/ ************************************************** *********** /
#include
#define n 100void main ()
{
INT SIEVE [N 1]; // n
// Step 1:
// Initialization (Sieve [i] = 0 means not in the screen, ie not a magpet; 1 is shown in the screen)
For (int i = 2; i <= n; i ) // start from 2, because 0 and 1 is not a magpet
SIEVE [I] = 1;
// STEP 2:
/ / The even number (2 multiple) is definitely not a prime number, so you should first screen it.
For (i = 2; i <= n / 2; i )
SIEVE [I * 2] = 0;
INT P = 2; // The first number is 2
// Step 3: Deleting the multiple of P from Sieve
While (p * p <= n)
{
// select a P
P = P 1;
While (Sieve [P] == 0)
P ;
INT T = P * P;
INT S = 2 * P;
While (t <= n)
{
SIEVE [T] = 0; // Delete
T = T S;
}
}
// step 4: output result
For (i = 2; i <= n; i )
{
IF (Sieve [i]! = 0)
{
Cout << i << ",";
}
}
}
three. Improve
In addition to it can be considered to change * 2 and / 2 outside of << 1 and >> 1, you can also bring together the first step and the second step.
//
// STEP 1 & 2:
For (INT i = 3; i <= n; i )
SIEVE [I] = I% 2;
Sieve [2] = 1; // 2 But the number!
//
Of course, there are other places to improve, this is not discussed here.
