# Multiscale Sieve for Smart Prime Generation and Application in Info-Security, IoT and Blockchain
## 3 Overview of the Algorithm  
After allocating the necessary memory, we consider the key elements and steps of the algorithm. Let us start with Formula (11). 1. \[\left(\prod_{j=1}^{m}p_{j}\right)\] (12) is the product of the first m primes, which changes at each level and serves as the basis for the generation of the multiscale prime candidate set. At each level, the addition of a new prime number to the product expands the set of candidates and, at the same time, automatically eliminates numbers that are multiples of this new prime, as we can see in Table 2. The process takes place at several levels, starting from an initial base that considers the first two prime numbers \(p_{1}=2\) and \(p_{2}=3\), with a base product that eliminates all numbers that are multiples of \(6\). Subsequently, at each level, a new prime number is introduced, which is multiplied by the product of the previous level, allowing us to systematically exclude multiples of this number, thus narrowing the field of possible numbers and facilitating the search for actual primes. For example, at the second level, with the addition of \(p_{3}=5\), the new product becomes \(6\cdot 5=30\), thus allowing the elimination of numbers that are multiples of \(30\). We call \(\boldsymbol{p}_{m+1}-p_{j}\) with \(j=m+1\) that is the prime number (already obtained at previous levels \(<m\)), which serves as a factor at the next level for the base \(\prod p_{j}\). At each level, k takes on all values in the range of \(1\) to \(k_{\max}\), excluding the lower or upper limit. The latter (\(k_{\max}\)) varies from level to level because it assumes the value of \(p_{m+1}\). To the product obtained between the \(\prod p_{j}\) and k, we subtract (or add) each prime number \(p_{i}\), belonging to the multiscale prime candidate sets of the previous levels, starting from the prime number \(p_{m+1}\). With the steps described, we have all of the elements available for the generation of multiscale prime candidate sets. Table 2 illustrates how, at each level, the number of candidate classes obtained \(\Lambda\), thanks to the multiscale approach, increases, but some of these classes are eliminated \(\Psi\) because they contain numbers that are multiples of the newly introduced prime numbers. For example, at the second level, with the product \(2\cdot 3\cdot 5=30\), there are \(10\) total classes, but two classes are eliminated because they include numbers that are multiples of \(5\), leaving eight remaining classes \(\Gamma\). Here, we give a pseudocode example of the generation Algorithm 1 and a numerical Example 1 to understand the procedure. The following Figure 1 represents the multiscale prime candidate set generated up to the third level (\(m=3\)), the numbers eliminated to reduce the research space (see Section 4.1), and the values assumed by the variables. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(\prod p_{i}\) & \# Classes \(\Lambda\) & **Deleted Classes \(\Psi\)** & **Remaining Classes** & **Eliminated Multiple** \\  & & & \(\Gamma\) & **of Ratio** \\ \hline \(2\cdot 3\) & 2 & 0 & 2 & 3 \\ \(2\cdot 3\cdot 5\) & 10 & 2 & 8 & 5 \\ \(2\cdot\ldots\cdot 7\) & 56 & 8 & 48 & 7 \\ \(2\cdot\ldots\cdot 11\) & 528 & 48 & 480 & 11 \\ \(2\cdot\ldots\cdot 13\) & 6240 & 480 & 5760 & 13 \\ \(2\cdot\ldots\cdot 17\) & 97,920 & 5760 & 92,160 & 17 \\ \(2\cdot\ldots\cdot 19\) & 1,751,040 & 92,160 & 1,658,880 & 19 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Overview of the reduction in prime candidate classes.