diff options
Diffstat (limited to 'samples/prime_tables.h')
| -rw-r--r-- | samples/prime_tables.h | 13 |
1 files changed, 8 insertions, 5 deletions
diff --git a/samples/prime_tables.h b/samples/prime_tables.h index 92ce16a..523c50b 100644 --- a/samples/prime_tables.h +++ b/samples/prime_tables.h @@ -26,9 +26,8 @@ // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -// -// Author: wan@google.com (Zhanyong Wan) -// Author: vladl@google.com (Vlad Losev) + + // This provides interface PrimeTable that determines whether a number is a // prime and determines a next prime number. This interface is used @@ -103,11 +102,15 @@ class PreCalculatedPrimeTable : public PrimeTable { ::std::fill(is_prime_, is_prime_ + is_prime_size_, true); is_prime_[0] = is_prime_[1] = false; - for (int i = 2; i <= max; i++) { + // Checks every candidate for prime number (we know that 2 is the only even + // prime). + for (int i = 2; i*i <= max; i += i%2+1) { if (!is_prime_[i]) continue; // Marks all multiples of i (except i itself) as non-prime. - for (int j = 2*i; j <= max; j += i) { + // We are starting here from i-th multiplier, because all smaller + // complex numbers were already marked. + for (int j = i*i; j <= max; j += i) { is_prime_[j] = false; } } |