# Multiscale Sieve for Smart Prime Generation and Application in Info-Security, IoT and Blockchain
## 5 Benchmark Setup  
The multiscale sieve algorithm was implemented in C and run on an M2 chip with a 64-bit ARM architecture and 16 GB RAM on a single thread at 3.5 GHz. The algorithm was compiled in an optimized way; through the C library <_time.h>_, and with the function clock, we measured the total time that the CPU required in executing the different inputs. Meanwhile, through the C library <_sys/resource.h>_ and with the function getrusage, we measured the maximum size of the resident set, which represented the maximum amount of physical memory used to execute the algorithm. In order to perform a comparative analysis, we used ancient and modern optimized versions of the sieve algorithms known to date, implemented in C. All sieve tests were executed under the same conditions as above. Graphs and Benchmark AnalysisAs can be seen from the following Table 3, less optimized algorithms or partial versions, such as the Segmented Sieve of Eratosthenes, Wheel Factorization, the Sieve of Sorenson, and many others, have been excluded, but optimized versions consisting of the union of several sieves have been included in order to make the comparison more competitive. All values are expressed in seconds (_s_). Each algorithm shown in the tables, as mentioned above, is an optimized version; it is clearly possible in some cases to perform further optimizations, which is due to the fact that there is no standard implementation of these algorithms. From an initial, purely computational analysis, we can see that the multiscale sieve is the most efficient for both small to medium and large inputs. Next, we graphically visualize in Figure 5 the growth in the execution time of the different sieving algorithms for a more complete analysis. Immediately, it can be seen that the multiscale sieve grows exponentially, performing better on every input, but, more importantly, the growth rate is significantly lower for very large inputs. This implies that, compared to other algorithms, the growth rate will always be lower and thus more efficient for larger and larger inputs. Furthermore, we can see in Table 4 how much faster the multiscale sieve is at a percentage level compared to each algorithm and input size. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Size of Input**} & **Sieve of** & **Sieve of** & \multicolumn{2}{c}{**Segmented Sieve of**} & \multirow{2}{*}{**Multiscale**} & **Primes** \\  & **Sundaram** & **Atkin–** & **Enerstein** & & **Factorization** & **Sieve** \\ \hline \(10^{6}\) & 0.00327 & 0.0057 & 0.0082 & 0.0057 & **0.0014** & 78,498 \\ \(10^{7}\) & 0.0327 & 0.0440 & 0.0398 & 0.0385 & **0.0150** & 664,579 \\ \(10^{8}\) & 0.5432 & 0.4608 & 0.2319 & 0.1971 & **0.0504** & 5,761,455 \\ \(10^{9}\) & 8.7509 & 5.2928 & 2.0829 & 1.6061 & **0.2758** & 50,847,535 \\ \(10^{10}\) & 116.5851 & 53.6592 & 22.0850 & 15.4788 & **3.2695** & 450,052,510 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Execution time benchmark comparison—ancient and modern sieves. It is also crucial to analyze the memory used by the algorithm during execution, which can impact the efficiency. The following Table 5 shows all maximum values of the resident memory used for each process execution, which includes all physical memory pages that the process currently has in RAM. This includes the stack memory, heap memory, BSS, data segments and code segments. All values are expressed in megabytes (_MB_). The Segmented Sieve of Eratosthenes is known for its distinct memory efficiency, along with other similar variants, such as the bitwise sieve. In fact, even in this comparison, it proves to be one of the most memory-efficient at every input size. Next, we graphically visualise in Figure 6 the growth in the memory usage of the different sieving algorithms for a more complete analysis.