 |
Python
1.0
|
|
Python
1.0
|
The Sieve of Eratosthenes (276-194 BC). More...
Functions | |
| def | setDebug (stat) |
| Set debugging on or off. More... | |
| def | sieve (n) |
| Returns a list with all primes up to n. More... | |
| def | sieve2 (n) |
| Memory efficient version, using bitarray. More... | |
| def | arrayF (n) |
| Prepare an array for factorization. More... | |
| def | factorization (x, F) |
| Return the factors of x, given an array with the smallest number that divides each integer (0, if the integer is prime) up to x. More... | |
| def | printArray (array) |
| Print the primes corresponding to a given array. More... | |
| def | getArray (array) |
| Return the primes corresponding to a given array. More... | |
| def | getTime (dsec) |
| Return the time in the format: hr:min:sec:msec. More... | |
| def | main (argv=None) |
| Main program for testing. More... | |
Variables | |
| int | MAXN = 32000000000 |
| Maximum integer value for n. More... | |
| int | MINN = 1000 |
| Value for switching to using sieve2. More... | |
| bool | debug__ = True |
| Debugging state. More... | |
The Sieve of Eratosthenes (276-194 BC).
Eratosthenes was invited by the Pharaoh Ptolemy III of Egypt, to be the chief librarian at the library of Alexandria, the most important in the ancient times.
He hold this position from 236 BC to his death.
The sieve is a simple, ancient algorithm for finding all prime numbers up to any given limit.
The algorithm iteratively marks as composite (i.e. not prime) the multiples of each prime, starting at 2, using only additions.
| def _04d_sieve.arrayF | ( | n | ) |
Prepare an array for factorization.
For every number up to n, we will remember the smallest prime that divides this number.
For n = 20, return:
[0, 0, 0, 0, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| n | number to factorize. |
Referenced by main().
| def _04d_sieve.factorization | ( | x, | |
| F | |||
| ) |
Return the factors of x, given an array with the smallest number that divides each integer (0, if the integer is prime) up to x.
If we know that one of the prime factors of x is p, then all the prime factors of x are p plus the decomposition of x/p.
Number x cannot have more than log x prime factors, because every prime factor is >= 2. Factorization by the above method works in O(log x) time complexity.
Note that consecutive factors will be presented in non-decreasing order. The amount of memory needed for large numbers is prohibitive.
For x = 20, F[20] = 2 -> [2]
x = 20/2 = 10, F[10] = 2 -> [2,2]
x = 10/2 = 5, F[5] = 0 -> [2,2,5]
| x | number to factorize. |
| F | factor array. |
Referenced by main().
| def _04d_sieve.getArray | ( | array | ) |
Return the primes corresponding to a given array.
| array | Array of prime numbers. |
| def _04d_sieve.getTime | ( | dsec | ) |
Return the time in the format: hr:min:sec:msec.
| dsec | number of seconds as a double. |
Referenced by main().
| def _04d_sieve.main | ( | argv = None | ) |
Main program for testing.
References arrayF(), deeper.deep_getsizeof(), factorization(), getTime(), _01d_dec2bin.input, printArray(), setDebug(), and sieve().
| def _04d_sieve.printArray | ( | array | ) |
Print the primes corresponding to a given array.
| array | Array of prime numbers. |
Referenced by main().
| def _04d_sieve.setDebug | ( | stat | ) |
| def _04d_sieve.sieve | ( | n | ) |
Returns a list with all primes up to n.
We're iterating through n numbers. Whenever we reach a prime p, we start iterating through the multiples of p up to n. For each prime, this takes n/p operations.
\( n\ \sum_{p\ prime\ \leq n} {{1} \over {p}} = n\ (ln ({ln {(n)}}) + M)\)
So we end up with the prime harmonic series up to n, which actually evaluates out to log(log(n)). The total complexity is then: O(n log(log(n)).
| n | a given positive integer. |
References sieve2().
Referenced by main().
| def _04d_sieve.sieve2 | ( | n | ) |
Memory efficient version, using bitarray.
For \(n = 1 \times 10^9\) (one billion).
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
Number of primes: 50847534 Number of bytes: 112 Total Number of bytes: 160 Run time: 0h:6m:42s:884ms
Factors of 1000000000 is: [2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5] Number of bytes: 8000000080
Total Number of bytes: 8000081728 Run time: 0h:4m:5s:482m
| n | a given positive integer. |
Referenced by sieve().
| bool _04d_sieve.debug__ = True |
Debugging state.
| int _04d_sieve.MAXN = 32000000000 |
Maximum integer value for n.
| int _04d_sieve.MINN = 1000 |
Value for switching to using sieve2.
1.8.20