# Multiscale Sieve for Smart Prime Generation and Application in Info-Security, IoT and Blockchain
## 1 Introduction
### Relevant Works and Starting Points  
A perfect number is commonly defined as an integer that equals the sum of its proper positive divisors, i.e., the sum of the divisors excluding the number itself. Equivalently, a perfect number is one that is half the sum of all of its positive divisors, i.e., \(\sigma(n)=2n\), where \(\sigma(n)\) represents the sum of the divisors of \(n\). It is worth highlighting that the first perfect number is \(6\), since its proper positive divisors are \(1\), \(2\), and \(3\), and their sum is \(1+2+3=6\). Through the work in [17], in [18], we proved that the generation of prime numbers can be seen as a deterministic process. In fact, we found the minimal representation, i.e., the most compact expression, to denote the set of prime numbers in \(\mathbb{N}\) in terms of the first perfect number. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Name of Sieve** & **Time Complexity** & **Space Complexity** \\ \hline Sieve of Eratosthenes & \(O(n\log\log n)\) & \(O(n)\) \\ Linear Sieve & \(O(n)\) & \(O(n)\) \\ Sieve of Sundaram & \(O(n\log n)\) & \(O(n)\) \\ Sieve of Atkin & \(O(n/\log\log n)\) & \(O(\sqrt{n})\) \\ Sieve of Sorenson & \(O(n)\) & \(O(n/\log n)\) \\ Segmented Sieve of Eratosthenes & \(O(n/\log\log n)\) & \(O(\sqrt{n})\) \\ with Wheel Factorization & \(O(n/\log\log n)\) & \(O(\sqrt{n})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Overview of some of the determnistic sieving algorithms. Let us introduce the sets:  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\] \[S_{2} =\{s_{2}=6k-4:k\in\mathbb{N}\};\] (2) \[S_{3} =\{s_{3}=6k-3:k\in\mathbb{N}\};\] (3) \[S_{4} =\{s_{4}=6k-2:k\in\mathbb{N}\};\] (4) \[X =\{x_{k}=6k-1:k\in\mathbb{N}\};\] (5) \[S_{6} =\{s_{6}=6k:k\in\mathbb{N}\};\] (6) \[Y =\{y_{k}=6k+1:k\in\mathbb{N}\}. \tag{7}\]  
Therefore, we can represent the set of natural numbers \(\mathbb{N}\) as follows:  
\[\mathbb{N}=\{1\}\cup S_{2}\cup S_{3}\cup S_{4}\cup X\cup S_{6}\cup Y \tag{8}\]  
In fact, \(S_{1}\) contains the same elements as \(Y\), except for the first element, which is 1. Moreover, the sets following \(Y\) share the same elements as the previous sets from \(S_{1}\) to \(Y\) (excluding the elements omitted due to the shift mod 6), since their elements are obtained by simply shifting those of the previous sets. We prove that the set of the prime candidates \(\bar{P}\) can be written as  
\[\bar{P}=\{2\}\cup\{3\}\cup X\cup Y \tag{9}\]  
Unfortunately, the sets \(X\) and \(Y\) also include composite numbers, such as positive integers that are multiples of 5 and others. Consequently, we have introduced selection rules to exclude composite numbers and obtain the complete set of prime numbers. Let us introduce the following two subsets \(X^{(-)}\subset X\) and \(Y^{(-)}\subset Y\):  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]0  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]1  
where  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]2  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]3  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]4  
The natural numbers \(x_{k}\) and \(y_{k}\) are composite if and only if \(x_{k}\in X^{(-)}\) and \(y_{k}\in Y^{(-)}\). Thus, we obtain the minimal explicit representation for the set of primes:  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]5  
where  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]6  
\[S_{1} =\{s_{1}=6k-5:k\in\mathbb{N}\}; \tag{1}\]7  
In [19], we introduced a novel method to estimate a number of prime candidates less than \(n\), utilizing a multiscale analysis or, alternatively, a tree-based approach. In [20], a multiscale approach is introduced to progressively improve the computing performance, starting with the sets \(6k\mp 1\). It is important to note that the choice of the number 6, or the class of remainders mod 6, is related to the fact that \(6=2\cdot 3\), the product of the first two prime numbers. This approach can be iterated by considering \(30=2\cdot 3\cdot 5\)\(210=2\cdot 3\cdot 5\cdot 7\), and so on.