[Open white]
This series of articles were originally published in our college's team newspaper. I feel that I don't have to waste it, so I'm attached to here, I belong to self-entertainment, this series is mainly to c beginners, there is nothing deep Theory and technology. Mainly talk about some common algorithms, programming principles, coding techniques, programming, and so on.
[This issue]
See all the prices in 1 to 10,000
[Analysis 1:]
After analyzing the topic, we can use a variable for the for cycle, all over the number of 1 to 10,000, and judge that the current I is not a magpet in the cycle. Understand by the rigidity: only the number of 1 and it itself is the number (excluding 1). We use the BOOL type variable isprime to record the current number is not a prime number, change the value from 2 to i, the variable is J. Note i is a complimentary; if all I% j is not equal to 0, it means that it is a magple number. According to the above description, we can write a program, see the "C Basics Tutorial" on page 443 to 444. The procedure in the book solves the problem correctly, but is it the fastest? Do not! There is such americ in the primary equivometric: Complex N If its two factors multiply N, then smaller factors are not more than √N; so we can put for (j = 2; j <= I / 2; J ) to change to For (j = 2; j <= (int) SQRT (i); J ) (of course, you need to include header file
// The following cycle is an odd FOR spread from 3 to 10,000 (i = 3; i <= max; i = 2;) {isprime = true; t = (int) SQRT (i); // See Explanation 2
// The following cycle body is used to determine whether I is a magmeter for (j = 2; j <= t; j ) {if (0 == (i% J)) {// See Explanation 3 isprime = false; Break }}}}} {Cout << i << ";}} return 0;} The following explanation about programming skills and habits: 1. Define 10000 to constant, this is a good idea, put the program many times in the program The number of repeated numbers define a constant amount. This way, when you suddenly want to require a number of rigid within 100,000, you only need to modify one: Constant definition. 2. Divide for (j = 2; j <= (int) SQRT (i); j ) {...}: t = (int) SQRT (i); for (j = 2; j <= t ; What is the benefit of j ) {...}? Each judgment (int) SQRT (i) that J is changed from 2 to √i has always been a value, but the computer does not know, he will only do what you make him: after each J , for i Make the opening, for the entire program, this is a large amount of operation, so before the cyclic body is placed, I only change the I value when it is changed. 3. 0 == (I% J), I believe many students like to write (I% J) == 0, and write it in hand, this is a common easy ignore, will play at runtime, let you Can't find and crazy mistakes. If you have the above habits, then you may write if (k = 1) ..., and the result is the condition is true! So, write constant on == to the left is a personal relatively recommended (not forced) Writing, when you accidentally write ==, the compiler will give you a "non-lvalue in assocign", then You only need to correct the error. Give the ability to find hidden mistakes to the compiler, let your own painful hand, the vague eye rest, should be the desire of every programming.
[Analysis 2:]
The screening method is to use the sieve to sieve the way, such as beans and sand together, because the sand grains, the beans are large, so we take the net size and suitable sieves, sieve the sand and leave the beans, this is the screening method. The mixture of the sand and beans to be treated is set to the elements to be treated, and the sieve is obtained to obtain the elements of the sand that are neither eligible, and the beans, which are closed, and the screening tool sieve is the condition of screening. If the conditional element (or set) is prone to availability, the scope is also limited, and a screening method can be used. The screening method has a famous method when seeking a natural number range is called an eratosthenes screening method, which is approximately as follows: For example, we have to find all the prime numbers 1 ~ 100, 1, not the prime number of course, in 2 to 100 去 2 2 2 (excluding 2), then scratch 3 multiples (not including 3), (4 is drawn) again to 5 multiple ..., until it is not more than 10 multiple, left The lower is the number. The above algorithm can be expressed as follows: 1. [Initialization] establishes a number of tables for 2 to max; 2. [Set IP 2], assign 2 to IP, prepare multiple multiple of IP; 3. [IP> √N?] If IP> √n, go to 6; 4. [Demult] Take the multiple of IP in the counting; 5. [Find a top priority] Find the first number of unpaired numbers as the IP value in the IP succession, and then return to 3; 6. [Print] The total number of tables is completed, print and end. ■ The following is a C implementation of the filter algorithm: #include [Conclusion] I hope that through this article, you understand how to analyze, solve, and improve it. And master the screening algorithm. If you are reading this article or learn from C , please send me an email: Bigbuddha@sina.com.
