First arrange n natural numbers in order. 1 is not a prime number, nor a compliance, to take it. The second number 2 is the number of prime numbers, and all the numbers behind 2 can be taken away. 2 The first number of the first is not drawn is 3, leave 3 left, and then all the numbers behind 3 can be taken away. 3 The number behind the first is 5, leave 5, and then all the numbers behind 5 can be scored. This has been done, and all the total number of no more than N will be sieved. The left is not exceeding the total number of n. Because the Greek writes the number on the panel of the Lara, it is necessary to remember the number, just after seeking the work, this many small points are like a screen, so it is image The method of Eratsteny is called "Eltosteri], referred to as" screening ".
For i = 0 to n z (i) = 0 Next
'Mark Multiples of i
For i = 2 to n / 2 for j = 2 * i to n Step i z (j) = 1 Next Next NEXT
'Count unmarked Numbers, Which Are Primes Dim NBR = 0
For i = 2 to n if z (i) = 0 THEN NBR = 1 end if Next
Other people are optimized for the above
For i = 2 to n / 2 if z (i) = 0 Then for j = 2 * i to n Step i z (j) = 1 Next End End End End End End End IX
--------------------------------------------------
Another algorithm
For i: = 3 to n do beg: = true; for j: = 2 to runk (SQR (i)) DO if i mod j = 0 THEN BEGIN OK: = FALSE; J: = Round (SQR (I) ); End; if ok dam i; END; The screening method is to obtain the number of prime numbers in 2 to SQR (n) in the first algorithm to make sieves, and there is an algorithm in the array s. For i: = runk (SQR (N)) to n DO begin ok: = true; for j: = 1 to k DO begin if s [j] <= round (SQR (i)) The beginning of i mod s K] = 0 THEN BEGIN OK: = FALSE; J: = K; END; END ELSE J: = K; End; IF OK THEN WRITELN (I); END; this time and space efficiency is superior to this article method.
-------------------------------------------------- ------------------
Personal view The last type of calculation should be better than the previous algorithm, but the former algorithm 2 is a shift calculation when the whole is entirely removed, and the next type of opening operation The potential will inevitably lead to several times the execution instruction, so it is estimated that the language is different, and there may be different gaps between the two.
Finally, what is the above content from the BLOG and the owner of others, I have no copyright, I only learn notes ..
