This project prints out the matrix of the first N prime number's multiplication. For instance the first 10 prime number's matrix looks like this:
2 3 5 7 11 13 17 19 23 29
3 9 15 21 33 39 51 57 69 87
5 15 25 35 55 65 85 95 115 145
7 21 35 49 77 91 119 133 161 203
11 33 55 77 121 143 187 209 253 319
13 39 65 91 143 169 221 247 299 377
17 51 85 119 187 221 289 323 391 493
19 57 95 133 209 247 323 361 437 551
23 69 115 161 253 299 391 437 529 667
29 87 145 203 319 377 493 551 667 841
You should have Docker installed on your system, with docker installed you should be abble to build the image and run it.
$make build
The default way to run the command is with:
$make run
which runs for 10 primes, if you want to generate more primes simply use:
$make run PRIMES=20
Changing the default value for prime numbers to generate the matrix
$make test
$make destroy
Considering that we are running code on N primes, and we can consider some constant initialization O(1)
(we are assuming that the maximum number fits on the size of the word of the computer, if not we need to consider Knuth's book, which is O(WR)
where W+1 is number of machine words in the quotient and R is number of machine words in remainder for the modulo operand) our pseudo code is like this:
matrix:
generate_primes(N)
initialize_matrix(N)
for x from 0->N-1:
initialize_matrix[x][0]
initialize_matrix[0][x]
for x from 0->N-1:
for y from x->N-1:
initialize_matrix[x][y]
initialize_matrix[y][x]
The complexy in time is O(generate_primes) + O(Nˆ2)
. O(generate_primes)
is checking the number with all the primes that are less than its square root, similar to what the siege of Erastothenes does, O(M log log M)
Where M is the maximum number generated. Which makes the complexity O(M log log M)
considering that we cannot predict the maximum number generated. With the maximum number bigger than the memory word our complexity goes for O(W R M log log M )
.
The complexity in space is O(Nˆ2)
considering that we need to store the matrix of results.
It is possible to optimize the generation of the primes more using other sieges even more: https://en.wikipedia.org/wiki/Generating_primes