Listing Prime Numbers Periodically

Han-Lin Li; Shu-Cherng Fang; Way Kuo; Nianrui Lin

doi:10.4236/apm.2025.154012

Advances in Pure Mathematics > Vol.15 No.4, April 2025

Listing Prime Numbers Periodically

Han-Lin Li¹

, Shu-Cherng Fang²

, Way Kuo³

, Nianrui Lin⁴

¹Department of Computer Science, City University of Hong Kong, Hong Kong, China.
²Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC, USA.
³Hong Kong Institute for Advanced Study and Department of Data Science, City University of Hong Kong, Hong Kong, China.
⁴Department of Systems Engineering, City University of Hong Kong, Hong Kong, China.
DOI: 10.4236/apm.2025.154012 PDF HTML XML 149 Downloads 1,128 Views Citations

Abstract

Over millennia, people have considered prime numbers as unpredictable and hard to list. This study confirms that all positive integers without factors of 2, 3, 5 and 7 can be regarded as the offspring of 48 roots in the interval [11, 220]. These roots are to generate a Factor-Pair Table composed of 48 columns, each of which forms a basic binary matrix to indicate the locations of composite numbers. For a given interval, these composites are removed via mapping effect. After primality checking of the rest of the numbers, we identify all primes within the interval. We then form a Formula of Primes for prime prediction. Moreover, the Periodic Table of Primes (PTP) [1] is reconstructed based on the proposed algorithm to illustrate the distribution of primes and composites.

Keywords

Prime Listing, Factor-Pair Table, Mapping Effect

Share and Cite:

Li, H.-L., Fang, S.-C., Kuo, W. and Lin, N.R. (2025) Listing Prime Numbers Periodically. Advances in Pure Mathematics, 15, 247-268. doi: 10.4236/apm.2025.154012.

1. Introduction

The problem of listing all primes up to a given limit has always been a challenging task. The prime number theorem [2] states that the prime-counting function $π (n)$ is approximated by $n / \log n$ when $n$ is large, but listing all primes in a given interval has been considered as a much more difficult problem.

Except for trial division, which is too time-consuming, most of the existing algorithms are designed for finding all primes from the start, namely, from 2 to the given limit. The ancient Sieve of Eratosthenes iteratively removes composites as the multiples of primes already found [3]. In one of his notes [4], Dijkstra proposed a prime number algorithm that is more space-saving than the Sieve of Eratosthenes and has lower time complexity than trial division. Among other variants of the Sieve of Eratosthenes, Atkin’s [5] and Pritchard’s [6] improve the algorithm with preprocessing efforts, but require a trade-off between time and space complexity.

In contrast, little has been done on the prime listing within a given interval that starts from a large number. Helfgott [7] introduced an improved version of the Sieve of Eratosthenes that can construct all primes in an interval $[n - Δ, n + Δ]$ in space $O (Δ)$ and time $O (Δ \log n)$ .

In this paper, we propose an efficient algorithm to list primes in a given interval that starts from any number. The algorithm is based on the Periodic Table of Primes (PTP) developed by Li et al. [1]. Although similar roots were proposed in 1982 as Wheel factorization [8], the PTP [1] is an infinite table generated from the Cyclic Table of Composites through rigorous mathematical proofs. Based on the algorithm presented in this paper, the PTP [1] is further reconstructed.

Our algorithm first restricts the numbers to be tested to a smaller subset, specifically those in the given interval and the PTP. Then, the mapping effect determines that, in expectation, more than 54.75% of them are composite numbers in constant time. Combined with existing efficient primality test algorithms, including the AKS primality test [9] and Miller-Rabin primality test [10] [11], it reveals the primality of the rest of the numbers and lists all primes in that given interval.

Notations

$N_{0} = {0, 1, 2, \dots}$ .
$N_{+} = {1, 2, 3, \dots}$ .
$Λ = {n \in N_{+} | n > 1 and n has no factors of 2, 3, 5 and 7}$ .
$S = {r_{i} | r_{i} is an integer, 11 \leq r_{i} \leq 220, r_{i} \in Λ}$

$= {r_{1} = 11, r_{2} = 13, r_{3} = 17, \dots, r_{48} = 211}$ .

$Q = {q_{j} | q_{j} = r_{j} \in S} = {q_{1} = 11, q_{2} = 13, q_{3} = 17, \dots, q_{48} = 211}$ .
${[a, b]}_{N} = {n \in N | a \leq n \leq b}$ .
$⌈ x ⌉$ = ceiling function of the smallest integer greater than or equal to x.
$⌊ x ⌋$ = floor function of the largest integer less than x.

2. Basic Theory

This study proposes a novel way, called Periodic-Table-of-Primes (PTP) method, to list all primes within a pre-specified integer interval. The deduction of this method is based on the following observations:

2.1. Roots of Integers

By choosing the first four primes, 2, 3, 5 and 7, we can group every $2 \times 3 \times 5 \times 7 = 210$ numbers in one period starting from 11, i.e., ${[11, 220]}_{N}, {[221, 430]}_{N}, {[431, 640]}_{N}, \dots$ . Within each of these periods, there are 48 numbers without factors of 2, 3, 5 and 7. In particular, in ${[11, 220]}_{N}$ , there exist 48 numbers called roots, and we denote

$\begin{array}{l} S = {r_{1} = 11, r_{2} = 13, r_{3} = 17, r_{4} = 19, r_{5} = 23, r_{6} = 29, r_{7} = 31, r_{8} = 37, r_{9} = 41, r_{10} = 43, \\ r_{11} = 47, r_{12} = 53, r_{13} = 59, r_{14} = 61, r_{15} = 67, r_{16} = 71, r_{17} = 73, r_{18} = 79, r_{19} = 83, \\ r_{20} = 89, r_{21} = 97, r_{22} = 101, r_{23} = 103, r_{24} = 107, r_{25} = 109, r_{26} = 113, r_{27} = 121, \\ r_{28} = 127, r_{29} = 131, r_{30} = 137, r_{31} = 139, r_{32} = 143, r_{33} = 149, r_{34} = 151, r_{35} = 157, \\ r_{36} = 163, r_{37} = 167, r_{38} = 169, r_{39} = 173, r_{40} = 179, r_{41} = 181, r_{42} = 187, r_{43} = 191, \\ r_{44} = 193, r_{45} = 197, r_{46} = 199, r_{47} = 209, r_{48} = 211} . \end{array}$

Theorem 1. For any number $α \in Λ$ , there exists a unique $r_{i} \in S$ and $k \in N_{0}$ such that

$\begin{matrix} α = r_{i} + 210 k \end{matrix}$ . (1)

From Theorem 1, we know that each number $α \in Λ$ has a root and a period. In other words, $α$ is the $k^{th}$ descendant of $r_{i}$ .

From notations indicating that $Q = S$ and $q_{j} = r_{j}$ , $j = 1, 2, \dots, 48$ , we can also know that any factor of $α$ can be expressed as $q_{j} + 210 θ$ , for some $q_{j} \in Q$ and $θ \in N_{0}$ . The following observation further analyzes the structure of $α$ ’s factors.

2.2. Factor-Pair Table with Generation Information

Given $q_{j} \in Q$ and $r_{i} \in S$ , denote $q_{\hat{j} | i}$ as the unique element in $Q$ such that $q_{j} \times q_{\hat{j} | i} - r_{i}$ is a multiplier of 210, where $i, j \in {1, 2, \dots, 48}$ . Here $(q_{j}, q_{\hat{j} | i})$ is called a factor-pair with respect to $r_{i}$ . We also observe there exists an integer

$\begin{matrix} t_{j | i} = \frac{q_{j} q_{\hat{j} | i} - r_{i}}{210} \end{matrix}$ (2)

to specify the generation of $r_{i}$ in which the descendant of $q_{j}$ and $q_{\hat{j} | i}$ , i.e., $q_{j} \times q_{\hat{j} | i}$ lies.

Collecting all $(q_{j}, q_{\hat{j} | i})$ and $t_{j | i}$ for all $i, j \in {1, 2, \dots, 48}$ together, we then form a Factor-Pair Table with generation information. It is a $48 \times 48$ table made of element $(q_{j}, q_{\hat{j} | i}), t_{j | i}$ .

We denote each column of the table as $V_{j}$ , where

$V_{j} = {((q_{j}, q_{\hat{j} | 1}), t_{j | 1}; \dots; (q_{j}, q_{\hat{j} | i}), t_{j | i}; \dots; (q_{j}, q_{\hat{j} | 48}), t_{j | 48})}^{T}$ for $j = 1, 2, 3, \dots, 48$ .

Take $j = 1$ for instance,

$V_{1} = {((11, 211), 11; (11, 173), 9; (11, 97), 5; (11, 59), 3; \dots; (11, 191), 9)}^{T}$ ,

where $(q_{1}, q_{\hat{1} | 1}, t_{1 | 1}) = (q_{1}, q_{48}, t_{1 | 1}) = (11, 211, 11)$ , as shown in Table 1.

The Factor-Pair Table with generation information has the following properties:

1) In each row of the table, there are 48 factor-pairs.

2) If $q_{j} = q_{\hat{j} | i}$ , then $(q_{j}, q_{\hat{j} | i})$ is called a co-factor-pair. Co-factor-pairs only exist in 6 rows of the table. In each row corresponding to $r_{18} = 79$ , $r_{25} = 109$ , $r_{27} = 121$ , $r_{34} = 151$ , $r_{38} = 169$ and $r_{48} = 211$ , there are 8 co-factor-pairs among the 48 factor-pairs.

Table 1. Factor-pair table with generation information.

				1		2		3		4		5	6	7	8	9	10	11	12	13	14	15	16
				11		13		17		19		23	29	31	37	41	43	47	53	59	61	67	71
1		11		(11, 211), 11		(13, 17), 1		(17, 13), 1		(19, 89), 8		(23, 37), 4	(29, 109), 15	(31, 41), 6	(37, 23), 4	(41, 31), 6	(43, 137), 28	(47, 103), 23	(53, 127), 32	(59, 139), 39	(61, 131), 38	(67, 113), 36	(71, 151), 51
2		13		(11, 173), 9		(13, 211), 13		(17, 149), 12		(19, 67), 6		(23, 101), 11	(29, 167), 23	(31, 163), 24	(37, 199), 35	(41, 113), 22	(43, 181), 37	(47, 179), 40	(53, 131), 33	(59, 107), 30	(61, 193), 56	(67, 19), 6	(71, 83), 28
3		17		(11, 97), 5		(13, 179), 11		(17, 211), 17		(19, 23), 2		(23, 19), 2	(29, 73), 10	(31, 197), 29	(37, 131), 23	(41, 67), 13	(43, 59), 12	(47, 121), 27	(53, 139), 35	(59, 43), 12	(61, 107), 31	(67, 41), 13	(71, 157), 53
4		19		(11, 59), 3		(13, 163), 10		(17, 137), 11		(19, 211), 19		(23, 83), 9	(29, 131), 18	(31, 109), 16	(37, 97), 17	(41, 149), 29	(43, 103), 21	(47, 197), 44	(53, 143), 36	(59, 11), 3	(61, 169), 49	(67, 157), 50	(71, 89), 30
5		23		(11, 193), 10		(13, 131), 8		(17, 199), 16		(19, 167), 15		(23, 211), 23	(29, 37), 5	(31, 143), 21	(37, 29), 5	(41, 103), 20	(43, 191), 39	(47, 139), 31	(53, 151), 38	(59, 157), 44	(61, 83), 24	(67, 179), 57	(71, 163), 55
6		29		(11, 79), 4		(13, 83), 5		(17, 187), 15		(19, 101), 9		(23, 193), 21	(29, 211), 29	(31, 89), 13	(37, 137), 24	(41, 139), 27	(43, 113), 23	(47, 157), 35	(53, 163), 41	(59, 61), 17	(61, 59), 17	(67, 107), 34	(71, 169), 57
7		31		(11, 41), 2		(13, 67), 4		(17, 113), 9		(19, 79), 7		(23, 47), 5	(29, 59), 8	(31, 211), 31	(37, 103), 18	(41, 11), 2	(43, 157), 32	(47, 23), 5	(53, 167), 42	(59, 29), 8	(61, 121), 35	(67, 13), 4	(71, 101), 34
8		37		(11, 137), 7		(13, 19), 1		(17, 101), 8		(19, 13), 1		(23, 29), 3	(29, 23), 3	(31, 157), 23	(37, 211), 37	(41, 47), 9	(43, 79), 16	(47, 41), 9	(53, 179), 45	(59, 143), 40	(61, 97), 28	(67, 151), 48	(71, 107), 36
9		41		(11, 61), 3		(13, 197), 12		(17, 163), 13		(19, 179), 16		(23, 157), 17	(29, 139), 19	(31, 191), 28	(37, 143), 25	(41, 211), 41	(43, 167), 34	(47, 193), 43	(53, 187), 47	(59, 79), 22	(61, 11), 3	(67, 173), 55	(71, 181), 61
10		43		(11, 23), 1		(13, 181), 11		(17, 89), 7		(19, 157), 14		(23, 11), 1	(29, 197), 27	(31, 103), 15	(37, 109), 19	(41, 83), 16	(43, 211), 43	(47, 59), 13	(53, 191), 48	(59, 47), 13	(61, 73), 21	(67, 79), 25	(71, 113), 38
11		47		(11, 157), 8		(13, 149), 9		(17, 151), 12		(19, 113), 10		(23, 139), 15	(29, 103), 14	(31, 137), 20	(37, 41), 7	(41, 37), 7	(43, 89), 18	(47, 211), 47	(53, 199), 50	(59, 193), 54	(61, 197), 57	(67, 101), 32	(71, 187), 63
12		53		(11, 43), 2		(13, 101), 6		(17, 139), 11		(19, 47), 4		(23, 121), 13	(29, 67), 9	(31, 83), 12	(37, 149), 26	(41, 73), 14	(43, 11), 2	(47, 19), 4	(53, 211), 53	(59, 97), 27	(61, 173), 50	(67, 29), 9	(71, 193), 65
13		59		(11, 139), 7		(13, 53), 3		(17, 127), 10		(19, 191), 17		(23, 103), 11	(29, 31), 4	(31, 29), 4	(37, 47), 8	(41, 109), 21	(43, 143), 29	(47, 37), 8	(53, 13), 3	(59, 211), 59	(61, 149), 43	(67, 167), 53	(71, 199), 67
14		61		(11, 101), 5		(13, 37), 2		(17, 53), 4		(19, 169), 15		(23, 167), 18	(29, 89), 12	(31, 151), 22	(37, 13), 2	(41, 191), 37	(43, 187), 38	(47, 113), 25	(53, 17), 4	(59, 179), 50	(61, 211), 61	(67, 73), 23	(71, 131), 44
15		67		(11, 197), 10		(13, 199), 12		(17, 41), 3		(19, 103), 9		(23, 149), 16	(29, 53), 7	(31, 97), 14	(37, 121), 21	(41, 17), 3	(43, 109), 22	(47, 131), 29	(53, 29), 7	(59, 83), 23	(61, 187), 54	(67, 211), 67	(71, 137), 46
16		71		(11, 121), 6		(13, 167), 10		(17, 103), 8		(19, 59), 5		(23, 67), 7	(29, 169), 23	(31, 131), 19	(37, 53), 9	(41, 181), 35	(43, 197), 40	(47, 73), 16	(53, 37), 9	(59, 19), 5	(61, 101), 29	(67, 23), 7	(71, 211), 71
17		73		(11, 83), 4		(13, 151), 9		(17, 29), 2		(19, 37), 3		(23, 131), 14	(29, 17), 2	(31, 43), 6	(37, 19), 3	(41, 53), 10	(43, 31), 6	(47, 149), 33	(53, 41), 10	(59, 197), 55	(61, 163), 47	(67, 139), 44	(71, 143), 48
18		79		(11, 179), 9		(13, 103), 6		(17, 17), 1		(19, 181), 16		(23, 113), 12	(29, 191), 26	(31, 199), 29	(37, 127), 22	(41, 89), 17	(43, 163), 33	(47, 167), 37	(53, 53), 13	(59, 101), 28	(61, 139), 40	(67, 67), 21	(71, 149), 50
19		83		(11, 103), 5		(13, 71), 4		(17, 79), 6		(19, 137), 12		(23, 31), 3	(29, 97), 13	(31, 23), 3	(37, 59), 10	(41, 43), 8	(43, 41), 8	(47, 109), 24	(53, 61), 15	(59, 37), 10	(61, 53), 15	(67, 89), 28	(71, 13), 4
20		89		(11, 199), 10		(13, 23), 1		(17, 67), 5		(19, 71), 6		(23, 13), 1	(29, 61), 8	(31, 179), 26	(37, 167), 29	(41, 79), 15	(43, 173), 35	(47, 127), 28	(53, 73), 18	(59, 151), 42	(61, 29), 8	(67, 17), 5	(71, 19), 6
21		97		(11, 47), 2		(13, 169), 10		(17, 191), 15		(19, 193), 17		(23, 59), 6	(29, 83), 11	(31, 37), 5	(37, 31), 5	(41, 197), 38	(43, 139), 28	(47, 11), 2	(53, 89), 22	(59, 23), 6	(61, 67), 19	(67, 61), 19	(71, 167), 56
22		101		(11, 181), 9		(13, 137), 8		(17, 43), 3		(19, 149), 13		(23, 187), 20	(29, 199), 27	(31, 71), 10	(37, 173), 30	(41, 151), 29	(43, 17), 3	(47, 163), 36	(53, 97), 24	(59, 169), 47	(61, 191), 55	(67, 83), 26	(71, 31), 10
23		103		(11, 143), 7		(13, 121), 7		(17, 179), 14		(19, 127), 11		(23, 41), 4	(29, 47), 6	(31, 193), 28	(37, 139), 24	(41, 23), 4	(43, 61), 12	(47, 29), 6	(53, 101), 25	(59, 137), 38	(61, 43), 12	(67, 199), 63	(71, 173), 58
24		107		(11, 67), 3		(13, 89), 5		(17, 31), 2		(19, 83), 7		(23, 169), 18	(29, 163), 22	(31, 17), 2	(37, 71), 12	(41, 187), 36	(43, 149), 30	(47, 181), 40	(53, 109), 27	(59, 73), 20	(61, 167), 48	(67, 11), 3	(71, 37), 12
25		109		(11, 29), 1		(13, 73), 4		(17, 167), 13		(19, 61), 5		(23, 23), 2	(29, 11), 1	(31, 139), 20	(37, 37), 6	(41, 59), 11	(43, 193), 39	(47, 47), 10	(53, 113), 28	(59, 41), 11	(61, 19), 5	(67, 127), 40	(71, 179), 60
26		113		(11, 163), 8		(13, 41), 2		(17, 19), 1		(19, 17), 1		(23, 151), 16	(29, 127), 17	(31, 173), 25	(37, 179), 31	(41, 13), 2	(43, 71), 14	(47, 199), 44	(53, 121), 30	(59, 187), 52	(61, 143), 41	(67, 149), 47	(71, 43), 14
27		121		(11, 11), 0		(13, 187), 11		(17, 143), 11		(19, 139), 12		(23, 197), 21	(29, 149), 20	(31, 31), 4	(37, 43), 7	(41, 131), 25	(43, 37), 7	(47, 83), 18	(53, 137), 34	(59, 59), 16	(61, 181), 52	(67, 193), 61	(71, 191), 64
28		127		(11, 107), 5		(13, 139), 8		(17, 131), 10		(19, 73), 6		(23, 179), 19	(29, 113), 15	(31, 187), 27	(37, 151), 26	(41, 167), 32	(43, 169), 34	(47, 101), 22	(53, 149), 37	(59, 173), 48	(61, 157), 45	(67, 121), 38	(71, 197), 66
29		131		(11, 31), 1		(13, 107), 6		(17, 193), 15		(19, 29), 2		(23, 97), 10	(29, 19), 2	(31, 11), 1	(37, 83), 14	(41, 121), 23	(43, 47), 9	(47, 43), 9	(53, 157), 39	(59, 109), 30	(61, 71), 20	(67, 143), 45	(71, 61), 20
30		137		(11, 127), 6		(13, 59), 3		(17, 181), 14		(19, 173), 15		(23, 79), 8	(29, 193), 26	(31, 167), 24	(37, 191), 33	(41, 157), 30	(43, 179), 36	(47, 61), 13	(53, 169), 42	(59, 13), 3	(61, 47), 13	(67, 71), 22	(71, 67), 22
31		139		(11, 89), 4		(13, 43), 2		(17, 107), 8		(19, 151), 13		(23, 143), 15	(29, 41), 5	(31, 79), 11	(37, 157), 27	(41, 29), 5	(43, 13), 2	(47, 137), 30	(53, 173), 43	(59, 191), 53	(61, 109), 31	(67, 187), 59	(71, 209), 70
32		143		(11, 13), 0		(13, 11), 0		(17, 169), 13		(19, 107), 9		(23, 61), 6	(29, 157), 21	(31, 113), 16	(37, 89), 15	(41, 193), 37	(43, 101), 20	(47, 79), 17	(53, 181), 45	(59, 127), 35	(61, 23), 6	(67, 209), 66	(71, 73), 24
33		149		(11, 109), 5		(13, 173), 10		(17, 157), 12		(19, 41), 3		(23, 43), 4	(29, 121), 16	(31, 59), 8	(37, 197), 34	(41, 19), 3	(43, 23), 4	(47, 97), 21	(53, 193), 48	(59, 31), 8	(61, 209), 60	(67, 137), 43	(71, 79), 26
34		151		(11, 71), 3		(13, 157), 9		(17, 83), 6		(19, 19), 1		(23, 107), 11	(29, 179), 24	(31, 181), 26	(37, 163), 28	(41, 101), 19	(43, 67), 13	(47, 173), 38	(53, 197), 49	(59, 209), 58	(61, 61), 17	(67, 43), 13	(71, 11), 3
35		157		(11, 167), 8		(13, 109), 6		(17, 71), 5		(19, 163), 14		(23, 89), 9	(29, 143), 19	(31, 127), 18	(37, 61), 10	(41, 137), 26	(43, 199), 40	(47, 191), 42	(53, 209), 52	(59, 113), 31	(61, 37), 10	(67, 181), 57	(71, 17), 5
36		163		(11, 53), 2		(13, 61), 3		(17, 59), 4		(19, 97), 8		(23, 71), 7	(29, 107), 14	(31, 73), 10	(37, 169), 29	(41, 173), 33	(43, 121), 24	(47, 209), 46	(53, 11), 2	(59, 17), 4	(61, 13), 3	(67, 109), 34	(71, 23), 7
37		167		(11, 187), 9		(13, 29), 1		(17, 121), 9		(19, 53), 4		(23, 199), 21	(29, 13), 1	(31, 107), 15	(37, 101), 17	(41, 127), 24	(43, 209), 42	(47, 151), 33	(53, 19), 4	(59, 163), 45	(61, 137), 39	(67, 131), 41	(71, 97), 32
38		169		(11, 149), 7		(13, 13), 0		(17, 47), 3		(19, 31), 2		(23, 53), 5	(29, 71), 9	(31, 19), 2	(37, 67), 11	(41, 209), 40	(43, 43), 8	(47, 17), 3	(53, 23), 5	(59, 131), 36	(61, 199), 57	(67, 37), 11	(71, 29), 9
39		173		(11, 73), 3		(13, 191), 11		(17, 109), 8		(19, 197), 17		(23, 181), 19	(29, 187), 25	(31, 53), 7	(37, 209), 36	(41, 163), 31	(43, 131), 26	(47, 169), 37	(53, 31), 7	(59, 67), 18	(61, 113), 32	(67, 59), 18	(71, 103), 34
40		179		(11, 169), 8		(13, 143), 8		(17, 97), 7		(19, 131), 11		(23, 163), 17	(29, 151), 20	(31, 209), 30	(37, 107), 18	(41, 199), 38	(43, 53), 10	(47, 187), 41	(53, 43), 10	(59, 181), 50	(61, 89), 25	(67, 197), 62	(71, 109), 36
41		181		(11, 131), 6		(13, 127), 7		(17, 23), 1		(19, 109), 9		(23, 17), 1	(29, 209), 28	(31, 121), 17	(37, 73), 12	(41, 71), 13	(43, 97), 19	(47, 53), 11	(53, 47), 11	(59, 149), 41	(61, 151), 43	(67, 103), 32	(71, 41), 13
42		187		(11, 17), 0		(13, 79), 4		(17, 11), 0		(19, 43), 3		(23, 209), 22	(29, 173), 23	(31, 67), 9	(37, 181), 31	(41, 107), 20	(43, 19), 3	(47, 71), 15	(53, 59), 14	(59, 53), 14	(61, 127), 36	(67, 31), 9	(71, 47), 15
43		191		(11, 151), 7		(13, 47), 2		(17, 73), 5		(19, 209), 18		(23, 127), 13	(29, 79), 10	(31, 101), 14	(37, 113), 19	(41, 61), 11	(43, 107), 21	(47, 13), 2	(53, 67), 16	(59, 199), 55	(61, 41), 11	(67, 53), 16	(71, 121), 40
44		193		(11, 113), 5		(13, 31), 1		(17, 209), 16		(19, 187), 16		(23, 191), 20	(29, 137), 18	(31, 13), 1	(37, 79), 13	(41, 143), 27	(43, 151), 30	(47, 89), 19	(53, 71), 17	(59, 167), 46	(61, 103), 29	(67, 169), 53	(71, 53), 17
45		197		(11, 37), 1		(13, 209), 12		(17, 61), 4		(19, 143), 12		(23, 109), 11	(29, 43), 5	(31, 47), 6	(37, 11), 1	(41, 97), 18	(43, 29), 5	(47, 31), 6	(53, 79), 19	(59, 103), 28	(61, 17), 4	(67, 191), 60	(71, 127), 42
46		199		(11, 209), 10		(13, 193), 11		(17, 197), 15		(19, 121), 10		(23, 173), 18	(29, 101), 13	(31, 169), 24	(37, 187), 32	(41, 179), 34	(43, 73), 14	(47, 107), 23	(53, 83), 20	(59, 71), 19	(61, 79), 22	(67, 97), 30	(71, 59), 19
47		209		(11, 19), 0		(13, 113), 6		(17, 37), 2		(19, 11), 0		(23, 73), 7	(29, 181), 24	(31, 149), 21	(37, 17), 2	(41, 169), 32	(43, 83), 16	(47, 67), 14	(53, 103), 25	(59, 121), 33	(61, 179), 51	(67, 47), 14	(71, 139), 46
48		211		(11, 191), 9		(13, 97), 5		(17, 173), 13		(19, 199), 17		(23, 137), 14	(29, 29), 3	(31, 61), 8	(37, 193), 33	(41, 41), 7	(43, 127), 25	(47, 143), 31	(53, 107), 26	(59, 89), 24	(61, 31), 8	(67, 163), 51	(71, 71), 23
			17		18		19		20		21		22	23	24	25	26	27	28	29	30	31	32
			73		79		83		89		97		101	103	107	109	113	121	127	131	137	139	143
1	11		(73, 167), 58		(79, 149), 56		(83, 157), 62		(89, 19), 8		(97, 143), 66		(101, 181), 87	(103, 47), 23	(107, 163), 83	(109, 29), 15	(113, 67), 36	(121, 191), 110	(127, 53), 32	(131, 61), 38	(137, 43), 28	(139, 59), 39	(143, 97), 66
2	13		(73, 121), 42		(79, 157), 59		(83, 71), 28		(89, 137), 58		(97, 169), 78		(101, 23), 11	(103, 151), 74	(107, 59), 30	(109, 187), 97	(113, 41), 22	(121, 73), 42	(127, 139), 84	(131, 53), 33	(137, 89), 58	(139, 127), 84	(143, 191), 130
3	17		(73, 29), 10		(79, 173), 65		(83, 109), 43		(89, 163), 69		(97, 11), 5		(101, 127), 61	(103, 149), 73	(107, 61), 31	(109, 83), 43	(113, 199), 107	(121, 47), 27	(127, 101), 61	(131, 37), 23	(137, 181), 118	(139, 53), 35	(143, 169), 115
4	19		(73, 193), 67		(79, 181), 68		(83, 23), 9		(89, 71), 30		(97, 37), 17		(101, 179), 86	(103, 43), 21	(107, 167), 85	(109, 31), 16	(113, 173), 93	(121, 139), 80	(127, 187), 113	(131, 29), 18	(137, 17), 11	(139, 121), 80	(143, 53), 36
5	23		(73, 101), 35		(79, 197), 74		(83, 61), 24		(89, 97), 41		(97, 89), 41		(101, 73), 35	(103, 41), 20	(107, 169), 86	(109, 137), 71	(113, 121), 65	(121, 113), 65	(127, 149), 90	(131, 13), 8	(137, 109), 71	(139, 47), 31	(143, 31), 21
6	29		(73, 173), 60		(79, 11), 4		(83, 13), 5		(89, 31), 13		(97, 167), 77		(101, 19), 9	(103, 143), 70	(107, 67), 34	(109, 191), 99	(113, 43), 23	(121, 179), 103	(127, 197), 119	(131, 199), 124	(137, 37), 24	(139, 41), 27	(143, 103), 70
7	31		(73, 127), 44		(79, 19), 7		(83, 137), 54		(89, 149), 63		(97, 193), 89		(101, 71), 34	(103, 37), 18	(107, 173), 88	(109, 139), 72	(113, 17), 9	(121, 61), 35	(127, 73), 44	(131, 191), 119	(137, 83), 54	(139, 109), 72	(143, 197), 134
8	37		(73, 199), 69		(79, 43), 16		(83, 89), 35		(89, 83), 35		(97, 61), 28		(101, 17), 8	(103, 139), 68	(107, 71), 36	(109, 193), 100	(113, 149), 80	(121, 127), 73	(127, 121), 73	(131, 167), 104	(137, 11), 7	(139, 103), 68	(143, 59), 40
9	41		(73, 107), 37		(79, 59), 22		(83, 127), 50		(89, 109), 46		(97, 113), 52		(101, 121), 58	(103, 137), 67	(107, 73), 37	(109, 89), 46	(113, 97), 52	(121, 101), 58	(127, 83), 50	(131, 151), 94	(137, 103), 67	(139, 29), 19	(143, 37), 25
10	43		(73, 61), 21		(79, 67), 25		(83, 41), 16		(89, 17), 7		(97, 139), 64		(101, 173), 83	(103, 31), 15	(107, 179), 91	(109, 37), 19	(113, 71), 38	(121, 193), 111	(127, 169), 102	(131, 143), 89	(137, 149), 97	(139, 97), 64	(143, 131), 89
11	47		(73, 179), 62		(79, 83), 31		(83, 79), 31		(89, 43), 18		(97, 191), 88		(101, 67), 32	(103, 29), 14	(107, 181), 92	(109, 143), 74	(113, 19), 10	(121, 167), 96	(127, 131), 79	(131, 127), 79	(137, 31), 20	(139, 23), 15	(143, 109), 74
12	53		(73, 41), 14		(79, 107), 40		(83, 31), 12		(89, 187), 79		(97, 59), 27		(101, 13), 6	(103, 131), 64	(107, 79), 40	(109, 197), 102	(113, 151), 81	(121, 23), 13	(127, 179), 108	(131, 103), 64	(137, 169), 110	(139, 17), 11	(143, 181), 123
13	59		(73, 113), 39		(79, 131), 49		(83, 193), 76		(89, 121), 51		(97, 137), 63		(101, 169), 81	(103, 23), 11	(107, 187), 95	(109, 41), 21	(113, 73), 39	(121, 89), 51	(127, 17), 10	(131, 79), 49	(137, 97), 63	(139, 11), 7	(143, 43), 29
14	61		(73, 67), 23		(79, 139), 52		(83, 107), 42		(89, 29), 12		(97, 163), 75		(101, 11), 5	(103, 127), 62	(107, 83), 42	(109, 199), 103	(113, 47), 25	(121, 181), 104	(127, 103), 62	(131, 71), 44	(137, 143), 93	(139, 79), 52	(143, 137), 93
15	67		(73, 139), 48		(79, 163), 61		(83, 59), 23		(89, 173), 73		(97, 31), 14		(101, 167), 80	(103, 19), 9	(107, 191), 97	(109, 43), 22	(113, 179), 96	(121, 37), 21	(127, 151), 91	(131, 47), 29	(137, 71), 46	(139, 73), 48	(143, 209), 142
16	71		(73, 47), 16		(79, 179), 67		(83, 97), 38		(89, 199), 84		(97, 83), 38		(101, 61), 29	(103, 17), 8	(107, 193), 98	(109, 149), 77	(113, 127), 68	(121, 11), 6	(127, 113), 68	(131, 31), 19	(137, 163), 106	(139, 209), 138	(143, 187), 127
17	73		(73, 211), 73		(79, 187), 70		(83, 11), 4		(89, 107), 45		(97, 109), 50		(101, 113), 54	(103, 121), 59	(107, 89), 45	(109, 97), 50	(113, 101), 54	(121, 103), 59	(127, 199), 120	(131, 23), 14	(137, 209), 136	(139, 67), 44	(143, 71), 48
18	79		(73, 73), 25		(79, 211), 79		(83, 173), 68		(89, 41), 17		(97, 187), 86		(101, 59), 28	(103, 13), 6	(107, 197), 100	(109, 151), 78	(113, 23), 12	(121, 169), 97	(127, 37), 22	(131, 209), 130	(137, 137), 89	(139, 61), 40	(143, 143), 97
19	83		(73, 191), 66		(79, 17), 6		(83, 211), 83		(89, 67), 28		(97, 29), 13		(101, 163), 78	(103, 11), 5	(107, 199), 101	(109, 47), 24	(113, 181), 97	(121, 143), 82	(127, 209), 126	(131, 193), 120	(137, 19), 12	(139, 197), 130	(143, 121), 82
20	89		(73, 53), 18		(79, 41), 15		(83, 163), 64		(89, 211), 89		(97, 107), 49		(101, 109), 52	(103, 113), 55	(107, 97), 49	(109, 101), 52	(113, 103), 55	(121, 209), 120	(127, 47), 28	(131, 169), 105	(137, 157), 102	(139, 191), 126	(143, 193), 131
21	97		(73, 79), 27		(79, 73), 27		(83, 29), 11		(89, 53), 22		(97, 211), 97		(101, 107), 51	(103, 109), 53	(107, 101), 51	(109, 103), 53	(113, 209), 112	(121, 157), 90	(127, 181), 109	(131, 137), 85	(137, 131), 85	(139, 43), 28	(143, 149), 101
22	101		(73, 197), 68		(79, 89), 33		(83, 67), 26		(89, 79), 33		(97, 53), 24		(101, 211), 101	(103, 107), 52	(107, 103), 52	(109, 209), 108	(113, 157), 84	(121, 131), 75	(127, 143), 86	(131, 121), 75	(137, 13), 8	(139, 179), 118	(143, 127), 86
23	103		(73, 151), 52		(79, 97), 36		(83, 191), 75		(89, 197), 83		(97, 79), 36		(101, 53), 25	(103, 211), 103	(107, 209), 106	(109, 157), 81	(113, 131), 70	(121, 13), 7	(127, 19), 11	(131, 113), 70	(137, 59), 38	(139, 37), 24	(143, 11), 7
24	107		(73, 59), 20		(79, 113), 42		(83, 19), 7		(89, 13), 5		(97, 131), 60		(101, 157), 75	(103, 209), 102	(107, 211), 107	(109, 53), 27	(113, 79), 42	(121, 197), 113	(127, 191), 115	(131, 97), 60	(137, 151), 98	(139, 173), 114	(143, 199), 135
25	109		(73, 13), 4		(79, 121), 45		(83, 143), 56		(89, 131), 55		(97, 157), 72		(101, 209), 100	(103, 103), 50	(107, 107), 54	(109, 211), 109	(113, 53), 28	(121, 79), 45	(127, 67), 40	(131, 89), 55	(137, 197), 128	(139, 31), 20	(143, 83), 56
26	113		(73, 131), 45		(79, 137), 51		(83, 181), 71		(89, 157), 66		(97, 209), 96		(101, 103), 49	(103, 101), 49	(107, 109), 55	(109, 107), 55	(113, 211), 113	(121, 53), 30	(127, 29), 17	(131, 73), 45	(137, 79), 51	(139, 167), 110	(143, 61), 41
27	121		(73, 157), 54		(79, 169), 63		(83, 47), 18		(89, 209), 88		(97, 103), 47		(101, 101), 48	(103, 97), 47	(107, 113), 57	(109, 109), 56	(113, 107), 57	(121, 211), 121	(127, 163), 98	(131, 41), 25	(137, 53), 34	(139, 19), 12	(143, 17), 11
28	127		(73, 19), 6		(79, 193), 72		(83, 209), 82		(89, 143), 60		(97, 181), 83		(101, 47), 22	(103, 199), 97	(107, 11), 5	(109, 163), 84	(113, 29), 15	(121, 67), 38	(127, 211), 127	(131, 17), 10	(137, 191), 124	(139, 13), 8	(143, 89), 60
29	131		(73, 137), 47		(79, 209), 78		(83, 37), 14		(89, 169), 71		(97, 23), 10		(101, 151), 72	(103, 197), 96	(107, 13), 6	(109, 59), 30	(113, 187), 100	(121, 41), 23	(127, 173), 104	(131, 211), 131	(137, 73), 47	(139, 149), 98	(143, 67), 45
30	137		(73, 209), 72		(79, 23), 8		(83, 199), 78		(89, 103), 43		(97, 101), 46		(101, 97), 46	(103, 89), 43	(107, 121), 61	(109, 113), 58	(113, 109), 58	(121, 107), 61	(127, 11), 6	(131, 187), 116	(137, 211), 137	(139, 143), 94	(143, 139), 94
31	139		(73, 163), 56		(79, 31), 11		(83, 113), 44		(89, 11), 4		(97, 127), 58		(101, 149), 71	(103, 193), 94	(107, 17), 8	(109, 61), 31	(113, 83), 44	(121, 199), 114	(127, 97), 58	(131, 179), 111	(137, 47), 30	(139, 211), 139	(143, 23), 15
32	143		(73, 71), 24		(79, 47), 17		(83, 151), 59		(89, 37), 15		(97, 179), 82		(101, 43), 20	(103, 191), 93	(107, 19), 9	(109, 167), 86	(113, 31), 16	(121, 173), 99	(127, 59), 35	(131, 163), 101	(137, 139), 90	(139, 137), 90	(143, 211), 143
33	149		(73, 143), 49		(79, 71), 26		(83, 103), 40		(89, 181), 76		(97, 47), 21		(101, 199), 95	(103, 83), 40	(107, 127), 64	(109, 11), 5	(113, 163), 87	(121, 29), 16	(127, 107), 64	(131, 139), 86	(137, 67), 43	(139, 131), 86	(143, 73), 49
34	151		(73, 97), 33		(79, 79), 29		(83, 17), 6		(89, 89), 37		(97, 73), 33		(101, 41), 19	(103, 187), 91	(107, 23), 11	(109, 169), 87	(113, 137), 73	(121, 121), 69	(127, 193), 116	(131, 131), 81	(137, 113), 73	(139, 199), 131	(143, 167), 113
35	157		(73, 169), 58		(79, 103), 38		(83, 179), 70		(89, 23), 9		(97, 151), 69		(101, 197), 94	(103, 79), 38	(107, 131), 66	(109, 13), 6	(113, 59), 31	(121, 187), 107	(127, 31), 18	(131, 107), 66	(137, 41), 26	(139, 193), 127	(143, 29), 19
36	163		(73, 31), 10		(79, 127), 47		(83, 131), 51		(89, 167), 70		(97, 19), 8		(101, 143), 68	(103, 181), 88	(107, 29), 14	(109, 67), 34	(113, 191), 102	(121, 43), 24	(127, 79), 47	(131, 83), 51	(137, 179), 116	(139, 187), 123	(143, 101), 68
37	167		(73, 149), 51		(79, 143), 53		(83, 169), 66		(89, 193), 81		(97, 71), 32		(101, 37), 17	(103, 179), 87	(107, 31), 15	(109, 173), 89	(113, 139), 74	(121, 17), 9	(127, 41), 24	(131, 67), 41	(137, 61), 39	(139, 113), 74	(143, 79), 53
38	169		(73, 103), 35		(79, 151), 56		(83, 83), 32		(89, 101), 42		(97, 97), 44		(101, 89), 42	(103, 73), 35	(107, 137), 69	(109, 121), 62	(113, 113), 60	(121, 109), 62	(127, 127), 76	(131, 59), 36	(137, 107), 69	(139, 181), 119	(143, 173), 117
39	173		(73, 11), 3		(79, 167), 62		(83, 121), 47		(89, 127), 53		(97, 149), 68		(101, 193), 92	(103, 71), 34	(107, 139), 70	(109, 17), 8	(113, 61), 32	(121, 83), 47	(127, 89), 53	(131, 43), 26	(137, 199), 129	(139, 107), 70	(143, 151), 102
40	179		(73, 83), 28		(79, 191), 71		(83, 73), 28		(89, 61), 25		(97, 17), 7		(101, 139), 66	(103, 173), 84	(107, 37), 18	(109, 71), 36	(113, 193), 103	(121, 149), 85	(127, 137), 82	(131, 19), 11	(137, 127), 82	(139, 101), 66	(143, 13), 8
41	181		(73, 37), 12		(79, 199), 74		(83, 197), 77		(89, 179), 75		(97, 43), 19		(101, 191), 91	(103, 67), 32	(107, 143), 72	(109, 19), 9	(113, 167), 89	(121, 31), 17	(127, 13), 7	(131, 11), 6	(137, 173), 112	(139, 169), 111	(143, 107), 72
42	187		(73, 109), 37		(79, 13), 4		(83, 149), 58		(89, 113), 47		(97, 121), 55		(101, 137), 65	(103, 169), 82	(107, 41), 20	(109, 73), 37	(113, 89), 47	(121, 97), 55	(127, 61), 36	(131, 197), 122	(137, 101), 65	(139, 163), 107	(143, 179), 121
43	191		(73, 17), 5		(79, 29), 10		(83, 187), 73		(89, 139), 58		(97, 173), 79		(101, 31), 14	(103, 167), 81	(107, 43), 21	(109, 179), 92	(113, 37), 19	(121, 71), 40	(127, 23), 13	(131, 181), 112	(137, 193), 125	(139, 89), 58	(143, 157), 106
44	193		(73, 181), 62		(79, 37), 13		(83, 101), 39		(89, 47), 19		(97, 199), 91		(101, 83), 39	(103, 61), 29	(107, 149), 75	(109, 127), 65	(113, 11), 5	(121, 163), 93	(127, 109), 65	(131, 173), 107	(137, 29), 18	(139, 157), 103	(143, 41), 27
45	197		(73, 89), 30		(79, 53), 19		(83, 139), 54		(89, 73), 30		(97, 41), 18		(101, 187), 89	(103, 59), 28	(107, 151), 76	(109, 23), 11	(113, 169), 90	(121, 137), 78	(127, 71), 42	(131, 157), 97	(137, 121), 78	(139, 83), 54	(143, 19), 12
46	199		(73, 43), 14		(79, 61), 22		(83, 53), 20		(89, 191), 80		(97, 67), 30		(101, 29), 13	(103, 163), 79	(107, 47), 23	(109, 181), 93	(113, 143), 76	(121, 19), 10	(127, 157), 94	(131, 149), 92	(137, 167), 108	(139, 151), 99	(143, 113), 76
47	209		(73, 23), 7		(79, 101), 37		(83, 43), 16		(89, 151), 63		(97, 197), 90		(101, 79), 37	(103, 53), 25	(107, 157), 79	(109, 131), 67	(113, 13), 6	(121, 59), 33	(127, 167), 100	(131, 109), 67	(137, 187), 121	(139, 71), 46	(143, 163), 110
48	211		(73, 187), 64		(79, 109), 40		(83, 167), 65		(89, 59), 24		(97, 13), 5		(101, 131), 62	(103, 157), 76	(107, 53), 26	(109, 79), 40	(113, 197), 105	(121, 151), 86	(127, 43), 25	(131, 101), 62	(137, 23), 14	(139, 139), 91	(143, 47), 31
			33		34		35		36		37		38	39	40	41	42	43	44	45	46	47	48
			149		151		157		163		167		169	173	179	181	187	191	193	197	199	209	211
1	11		(149, 79), 56		(151, 71), 51		(157, 83), 62		(163, 107), 83		(167, 73), 58		(169, 179), 144	(173, 187), 154	(179, 169), 144	(181, 101), 87	(187, 173), 154	(191, 121), 110	(193, 197), 181	(197, 193), 181	(199, 209), 198	(209, 199), 198	(211, 11), 11
2	13		(149, 17), 12		(151, 103), 74		(157, 79), 59		(163, 31), 24		(167, 29), 23		(169, 97), 78	(173, 11), 9	(179, 47), 40	(181, 43), 37	(187, 109), 97	(191, 143), 130	(193, 61), 56	(197, 209), 196	(199, 37), 35	(209, 197), 196	(211, 13), 13
3	17		(149, 103), 73		(151, 167), 120		(157, 71), 53		(163, 89), 69		(167, 151), 120		(169, 143), 115	(173, 79), 65	(179, 13), 11	(181, 137), 118	(187, 191), 170	(191, 187), 170	(193, 209), 192	(197, 31), 29	(199, 113), 107	(209, 193), 192	(211, 17), 17
4	19		(149, 41), 29		(151, 199), 143		(157, 67), 50		(163, 13), 10		(167, 107), 85		(169, 61), 49	(173, 113), 93	(179, 101), 86	(181, 79), 68	(187, 127), 113	(191, 209), 190	(193, 73), 67	(197, 47), 44	(199, 151), 143	(209, 191), 190	(211, 19), 19
5	23		(149, 127), 90		(151, 53), 38		(157, 59), 44		(163, 71), 55		(167, 19), 15		(169, 107), 86	(173, 181), 149	(179, 67), 57	(181, 173), 149	(187, 209), 186	(191, 43), 39	(193, 11), 10	(197, 79), 74	(199, 17), 16	(209, 187), 186	(211, 23), 23
6	29		(149, 151), 107		(151, 149), 107		(157, 47), 35		(163, 53), 41		(167, 97), 77		(169, 71), 57	(173, 73), 60	(179, 121), 103	(181, 209), 180	(187, 17), 15	(191, 109), 99	(193, 23), 21	(197, 127), 119	(199, 131), 124	(209, 181), 180	(211, 29), 29
7	31		(149, 89), 63		(151, 181), 130		(157, 43), 32		(163, 187), 145		(167, 53), 42		(169, 199), 160	(173, 107), 88	(179, 209), 178	(181, 151), 130	(187, 163), 145	(191, 131), 119	(193, 97), 89	(197, 143), 134	(199, 169), 160	(209, 179), 178	(211, 31), 31
8	37		(149, 113), 80		(151, 67), 48		(157, 31), 23		(163, 169), 131		(167, 131), 104		(169, 163), 131	(173, 209), 172	(179, 53), 45	(181, 187), 161	(187, 181), 161	(191, 197), 179	(193, 109), 100	(197, 191), 179	(199, 73), 69	(209, 173), 172	(211, 37), 37
9	41		(149, 199), 141		(151, 131), 94		(157, 23), 17		(163, 17), 13		(167, 43), 34		(169, 209), 168	(173, 67), 55	(179, 19), 16	(181, 71), 61	(187, 53), 47	(191, 31), 28	(193, 47), 43	(197, 13), 12	(199, 149), 141	(209, 169), 168	(211, 41), 41
10	43		(149, 137), 97		(151, 163), 117		(157, 19), 14		(163, 151), 117		(167, 209), 166		(169, 127), 102	(173, 101), 83	(179, 107), 91	(181, 13), 11	(187, 199), 177	(191, 53), 48	(193, 121), 111	(197, 29), 27	(199, 187), 177	(209, 167), 166	(211, 43), 43
11	47		(149, 13), 9		(151, 17), 12		(157, 11), 8		(163, 209), 162		(167, 121), 96		(169, 173), 139	(173, 169), 139	(179, 73), 62	(181, 107), 92	(187, 71), 63	(191, 97), 88	(193, 59), 54	(197, 61), 57	(199, 53), 50	(209, 163), 162	(211, 47), 47
12	53		(149, 37), 26		(151, 113), 81		(157, 209), 156		(163, 191), 148		(167, 199), 158		(169, 137), 110	(173, 61), 50	(179, 127), 108	(181, 143), 123	(187, 89), 79	(191, 163), 148	(193, 71), 65	(197, 109), 102	(199, 167), 158	(209, 157), 156	(211, 53), 53
13	59		(149, 61), 43		(151, 209), 150		(157, 197), 147		(163, 173), 134		(167, 67), 53		(169, 101), 81	(173, 163), 134	(179, 181), 154	(181, 179), 154	(187, 107), 95	(191, 19), 17	(193, 83), 76	(197, 157), 147	(199, 71), 67	(209, 151), 150	(211, 59), 59
14	61		(149, 209), 148		(151, 31), 22		(157, 193), 144		(163, 97), 75		(167, 23), 18		(169, 19), 15	(173, 197), 162	(179, 59), 50	(181, 121), 104	(187, 43), 38	(191, 41), 37	(193, 157), 144	(197, 173), 162	(199, 109), 103	(209, 149), 148	(211, 61), 61
15	67		(149, 23), 16		(151, 127), 91		(157, 181), 135		(163, 79), 61		(167, 101), 80		(169, 193), 155	(173, 89), 73	(179, 113), 96	(181, 157), 135	(187, 61), 54	(191, 107), 97	(193, 169), 155	(197, 11), 10	(199, 13), 12	(209, 143), 142	(211, 67), 67
16	71		(149, 109), 77		(151, 191), 137		(157, 173), 129		(163, 137), 106		(167, 13), 10		(169, 29), 23	(173, 157), 129	(179, 79), 67	(181, 41), 35	(187, 143), 127	(191, 151), 137	(193, 107), 98	(197, 43), 40	(199, 89), 84	(209, 139), 138	(211, 71), 71
17	73		(149, 47), 33		(151, 13), 9		(157, 169), 126		(163, 61), 47		(167, 179), 142		(169, 157), 126	(173, 191), 157	(179, 167), 142	(181, 193), 166	(187, 79), 70	(191, 173), 157	(193, 181), 166	(197, 59), 55	(199, 127), 120	(209, 137), 136	(211, 73), 73
18	79		(149, 71), 50		(151, 109), 78		(157, 157), 117		(163, 43), 33		(167, 47), 37		(169, 121), 97	(173, 83), 68	(179, 11), 9	(181, 19), 16	(187, 97), 86	(191, 29), 26	(193, 193), 177	(197, 107), 100	(199, 31), 29	(209, 131), 130	(211, 79), 79
19	83		(149, 157), 111		(151, 173), 124		(157, 149), 111		(163, 101), 78		(167, 169), 134		(169, 167), 134	(173, 151), 124	(179, 187), 159	(181, 113), 97	(187, 179), 159	(191, 73), 66	(193, 131), 120	(197, 139), 130	(199, 107), 101	(209, 127), 126	(211, 83), 83
20	89		(149, 181), 128		(151, 59), 42		(157, 137), 102		(163, 83), 64		(167, 37), 29		(169, 131), 105	(173, 43), 35	(179, 31), 26	(181, 149), 128	(187, 197), 175	(191, 139), 126	(193, 143), 131	(197, 187), 175	(199, 11), 10	(209, 121), 120	(211, 89), 89
21	97		(149, 143), 101		(151, 187), 134		(157, 121), 90		(163, 199), 154		(167, 71), 56		(169, 13), 10	(173, 179), 147	(179, 173), 147	(181, 127), 109	(187, 151), 134	(191, 17), 15	(193, 19), 17	(197, 41), 38	(199, 163), 154	(209, 113), 112	(211, 97), 97
22	101		(149, 19), 13		(151, 41), 29		(157, 113), 84		(163, 47), 36		(167, 193), 153		(169, 59), 47	(173, 37), 30	(179, 139), 118	(181, 11), 9	(187, 23), 20	(191, 61), 55	(193, 167), 153	(197, 73), 68	(199, 29), 27	(209, 109), 108	(211, 101), 101
23	103		(149, 167), 118		(151, 73), 52		(157, 109), 81		(163, 181), 140		(167, 149), 118		(169, 187), 150	(173, 71), 58	(179, 17), 14	(181, 163), 140	(187, 169), 150	(191, 83), 75	(193, 31), 28	(197, 89), 83	(199, 67), 63	(209, 107), 106	(211, 103), 103
24	107		(149, 43), 30		(151, 137), 98		(157, 101), 75		(163, 29), 22		(167, 61), 48		(169, 23), 18	(173, 139), 114	(179, 193), 164	(181, 47), 40	(187, 41), 36	(191, 127), 115	(193, 179), 164	(197, 121), 113	(199, 143), 135	(209, 103), 102	(211, 107), 107
25	109		(149, 191), 135		(151, 169), 121		(157, 97), 72		(163, 163), 126		(167, 17), 13		(169, 151), 121	(173, 173), 142	(179, 71), 60	(181, 199), 171	(187, 187), 166	(191, 149), 135	(193, 43), 39	(197, 137), 128	(199, 181), 171	(209, 101), 100	(211, 109), 109
26	113		(149, 67), 47		(151, 23), 16		(157, 89), 66		(163, 11), 8		(167, 139), 110		(169, 197), 158	(173, 31), 25	(179, 37), 31	(181, 83), 71	(187, 59), 52	(191, 193), 175	(193, 191), 175	(197, 169), 158	(199, 47), 44	(209, 97), 96	(211, 113), 113
27	121		(149, 29), 20		(151, 151), 108		(157, 73), 54		(163, 127), 98		(167, 173), 137		(169, 79), 63	(173, 167), 137	(179, 179), 152	(181, 61), 52	(187, 13), 11	(191, 71), 64	(193, 67), 61	(197, 23), 21	(199, 199), 188	(209, 89), 88	(211, 121), 121
28	127		(149, 53), 37		(151, 37), 26		(157, 61), 45		(163, 109), 84		(167, 41), 32		(169, 43), 34	(173, 59), 48	(179, 23), 19	(181, 97), 83	(187, 31), 27	(191, 137), 124	(193, 79), 72	(197, 71), 66	(199, 103), 97	(209, 83), 82	(211, 127), 127
29	131		(149, 139), 98		(151, 101), 72		(157, 53), 39		(163, 167), 129		(167, 163), 129		(169, 89), 71	(173, 127), 104	(179, 199), 169	(181, 191), 164	(187, 113), 100	(191, 181), 164	(193, 17), 15	(197, 103), 96	(199, 179), 169	(209, 79), 78	(211, 131), 131
30	137		(149, 163), 115		(151, 197), 141		(157, 41), 30		(163, 149), 115		(167, 31), 24		(169, 53), 42	(173, 19), 15	(179, 43), 36	(181, 17), 14	(187, 131), 116	(191, 37), 33	(193, 29), 26	(197, 151), 141	(199, 83), 78	(209, 73), 72	(211, 137), 137
31	139		(149, 101), 71		(151, 19), 13		(157, 37), 27		(163, 73), 56		(167, 197), 156		(169, 181), 145	(173, 53), 43	(179, 131), 111	(181, 169), 145	(187, 67), 59	(191, 59), 53	(193, 103), 94	(197, 167), 156	(199, 121), 114	(209, 71), 70	(211, 139), 139
32	143		(149, 187), 132		(151, 83), 59		(157, 29), 21		(163, 131), 101		(167, 109), 86		(169, 17), 13	(173, 121), 99	(179, 97), 82	(181, 53), 45	(187, 149), 132	(191, 103), 93	(193, 41), 37	(197, 199), 186	(199, 197), 186	(209, 67), 66	(211, 143), 143
33	149		(149, 211), 149		(151, 179), 128		(157, 17), 12		(163, 113), 87		(167, 187), 148		(169, 191), 153	(173, 13), 10	(179, 151), 128	(181, 89), 76	(187, 167), 148	(191, 169), 153	(193, 53), 48	(197, 37), 34	(199, 101), 95	(209, 61), 60	(211, 149), 149
34	151		(149, 149), 105		(151, 211), 151		(157, 13), 9		(163, 37), 28		(167, 143), 113		(169, 109), 87	(173, 47), 38	(179, 29), 24	(181, 31), 26	(187, 103), 91	(191, 191), 173	(193, 127), 116	(197, 53), 49	(199, 139), 131	(209, 59), 58	(211, 151), 151
35	157		(149, 173), 122		(151, 97), 69		(157, 211), 157		(163, 19), 14		(167, 11), 8		(169, 73), 58	(173, 149), 122	(179, 83), 70	(181, 67), 57	(187, 121), 107	(191, 47), 42	(193, 139), 127	(197, 101), 94	(199, 43), 40	(209, 53), 52	(211, 157), 157
36	163		(149, 197), 139		(151, 193), 138		(157, 199), 148		(163, 211), 163		(167, 89), 70		(169, 37), 29	(173, 41), 33	(179, 137), 116	(181, 103), 88	(187, 139), 123	(191, 113), 102	(193, 151), 138	(197, 149), 139	(199, 157), 148	(209, 47), 46	(211, 163), 163
37	167		(149, 73), 51		(151, 47), 33		(157, 191), 142		(163, 59), 45		(167, 211), 167		(169, 83), 66	(173, 109), 89	(179, 103), 87	(181, 197), 169	(187, 11), 9	(191, 157), 142	(193, 89), 81	(197, 181), 169	(199, 23), 21	(209, 43), 42	(211, 167), 167
38	169		(149, 11), 7		(151, 79), 56		(157, 187), 139		(163, 193), 149		(167, 167), 132		(169, 211), 169	(173, 143), 117	(179, 191), 162	(181, 139), 119	(187, 157), 139	(191, 179), 162	(193, 163), 149	(197, 197), 184	(199, 61), 57	(209, 41), 40	(211, 169), 169
39	173		(149, 97), 68		(151, 143), 102		(157, 179), 133		(163, 41), 31		(167, 79), 62		(169, 47), 37	(173, 211), 173	(179, 157), 133	(181, 23), 19	(187, 29), 25	(191, 13), 11	(193, 101), 92	(197, 19), 17	(199, 137), 129	(209, 37), 36	(211, 173), 173
40	179		(149, 121), 85		(151, 29), 20		(157, 167), 124		(163, 23), 17		(167, 157), 124		(169, 11), 8	(173, 103), 84	(179, 211), 179	(181, 59), 50	(187, 47), 41	(191, 79), 71	(193, 113), 103	(197, 67), 62	(199, 41), 38	(209, 31), 30	(211, 179), 179
41	181		(149, 59), 41		(151, 61), 43		(157, 163), 121		(163, 157), 121		(167, 113), 89		(169, 139), 111	(173, 137), 112	(179, 89), 75	(181, 211), 181	(187, 193), 171	(191, 101), 91	(193, 187), 171	(197, 83), 77	(199, 79), 74	(209, 29), 28	(211, 181), 181
42	187		(149, 83), 58		(151, 157), 112		(157, 151), 112		(163, 139), 107		(167, 191), 151		(169, 103), 82	(173, 29), 23	(179, 143), 121	(181, 37), 31	(187, 211), 187	(191, 167), 151	(193, 199), 182	(197, 131), 122	(199, 193), 182	(209, 23), 22	(211, 187), 187
43	191		(149, 169), 119		(151, 11), 7		(157, 143), 106		(163, 197), 152		(167, 103), 81		(169, 149), 119	(173, 97), 79	(179, 109), 92	(181, 131), 112	(187, 83), 73	(191, 211), 191	(193, 137), 125	(197, 163), 152	(199, 59), 55	(209, 19), 18	(211, 191), 191
44	193		(149, 107), 75		(151, 43), 30		(157, 139), 103		(163, 121), 93		(167, 59), 46		(169, 67), 53	(173, 131), 107	(179, 197), 167	(181, 73), 62	(187, 19), 16	(191, 23), 20	(193, 211), 193	(197, 179), 167	(199, 97), 91	(209, 17), 16	(211, 193), 193
45	197		(149, 193), 136		(151, 107), 76		(157, 131), 97		(163, 179), 138		(167, 181), 143		(169, 113), 90	(173, 199), 163	(179, 163), 138	(181, 167), 143	(187, 101), 89	(191, 67), 60	(193, 149), 136	(197, 211), 197	(199, 173), 163	(209, 13), 12	(211, 197), 197
46	199		(149, 131), 92		(151, 139), 99		(157, 127), 94		(163, 103), 79		(167, 137), 108		(169, 31), 24	(173, 23), 18	(179, 41), 34	(181, 109), 93	(187, 37), 32	(191, 89), 80	(193, 13), 11	(197, 17), 15	(199, 211), 199	(209, 11), 10	(211, 199), 199
47	209		(149, 31), 21		(151, 89), 63		(157, 107), 79		(163, 143), 110		(167, 127), 100		(169, 41), 32	(173, 193), 158	(179, 61), 51	(181, 29), 24	(187, 137), 121	(191, 199), 180	(193, 173), 158	(197, 97), 90	(199, 191), 180	(209, 211), 209	(211, 209), 209
48	211		(149, 179), 126		(151, 121), 86		(157, 103), 76		(163, 67), 51		(167, 83), 65		(169, 169), 135	(173, 17), 13	(179, 149), 126	(181, 181), 155	(187, 73), 64	(191, 11), 9	(193, 37), 33	(197, 113), 105	(199, 19), 17	(209, 209), 207	(211, 211), 211

3) If $(q_{j}, q_{\hat{j} | i})$ is not a co-factor-pair, then $(q_{\hat{j} | i}, q_{j})$ is a factor-pair with the same generation $t_{j | i}$ as $(q_{j}, q_{\hat{j} | i})$ .

4) For any $j$ and $i$ , we have $t_{j | i} \leq r_{j}$ .

We found that the factors of a composite number $α$ are closely related to factor-pairs in the Factor-Pair Table with generation information:

Theorem 2. If $q_{j} + 210 θ$ ( $θ \in N_{0}$ ) is a factor of $α = r_{i} + 210 k$ , then

$\frac{α}{q_{j} + 210 θ}$ is a descendant of $q_{\hat{j} | i}$ , i.e.,

$\begin{matrix} \frac{α}{q_{j} + 210 θ} = q_{\hat{j} | i} + 210 \hat{θ} \end{matrix}$ . (3)

Theorems 1 and 2 confirm that any composite number $α$ without factors of 2, 3, 5 and 7 can be written as

$\begin{matrix} α = r_{i} + 210 k = (q_{j} + 210 θ) (q_{\hat{j} | i} + 210 \hat{θ}) \end{matrix}$ , (4)

where $θ, \hat{θ} \in N_{0}$ and $j \in {1, 2, \dots, 48}$ .

From Equation (4), we have

$\begin{matrix} r_{i} + 210 k = q_{j} q_{\hat{j} | i} + 210 θ q_{\hat{j} | i} + 210 \hat{θ} q_{j} + 210^{2} θ \hat{θ} \end{matrix}$ . (5)

Combining Equations (2) and (5), we get

$\begin{matrix} t_{j | i} = k - θ q_{\hat{j} | i} - \hat{θ} q_{j} - 210 θ \hat{θ} \end{matrix}$ . (6)

When $j$ is fixed, Equation (6) is a quadratic equation with only two unknowns $θ$ and $\hat{θ}$ in $N_{0}$ .

Theorem 3. To check whether a number $α = r_{i} + 210 k$ is a composite number, it suffices to check if Equation (6) has a solution $(θ, \hat{θ}) \in N_{0} \times N_{0}$ for some $j \in {1, 2, \dots, 48}$ .

We then propose an algorithm to solve the equation.

Without loss of generality, we assume $q_{j} + 210 θ \leq q_{\hat{j} | i} + 210 \hat{θ}$ , since we can replace $q_{j}$ and $θ$ with $q_{\hat{j} | i}$ and $\hat{θ}$ correspondingly if $q_{j} + 210 θ > q_{\hat{j} | i} + 210 \hat{θ}$ . Given $α = (q_{j} + 210 θ) (q_{\hat{j} | i} + 210 \hat{θ})$ , we see

$\begin{matrix} q_{j} + 210 θ \leq \sqrt{α} \end{matrix}$ . (7)

Therefore,

$\begin{matrix} θ \leq \frac{\sqrt{α} - q_{j}}{210} \leq \frac{\sqrt{α}}{210} \end{matrix}$ . (8)

We can derive a direct corollary from Theorem 3:

Corollary 1. Checking whether a number $α = r_{i} + 210 k \in Λ$ is a composite number is equivalent to checking if

$\begin{matrix} \hat{θ} = \frac{k - t_{j | i} - θ q_{\hat{j} | i}}{q_{j} + 210 θ} \end{matrix}$ (9)

is an integer for some $θ \in {0, 1, \dots, ⌈ \frac{\sqrt{α}}{210} ⌉}$ .

Based on this Corollary, we can develop a new algorithm for primality test:

Algorithm 1:

Step 1: Input a natural number $α$ . If $α$ is divisible by 2, 3, 5 or 7, then $α$ is not a prime, and the algorithm terminates.

Step 2: Set $r_{i} = α - ⌊ \frac{α - 10}{210} ⌋ \times 210$ .

Step 3: For each $j \in {1, 2, \dots, 48}$ , examine the Factor-Pair Table with generation information for the factor pair $(q_{j}, q_{\hat{j} | i})$ and generation $t_{j | i}$ . For each $θ \in {0, 1, \dots, ⌊ \frac{\sqrt{α}}{210} ⌋}$ , compute Equation (9). According to Corollary 1, if $\hat{θ} \in N_{0}$ , then $α$ is not a prime, and the algorithm terminates.

Step 4: If the loop completes (having traversed all $j$ ) without finding a solution, then $α$ is a prime.

The following theorem gives the complexity of Algorithm 1:

Theorem 4. Algorithm 1 involves at most 48 linear searches over $⌈ \frac{\sqrt{α}}{210} ⌉ + 1$ integer values. In other words, the worst case is searching through about $\sqrt{α} / 4$ integer values.

However, to list all primes within a pre-specified interval, the above algorithm for primality test costs too much time. Therefore, we need to find a more efficient way to locate primes.

3. Method

Notice that in a given interval, primes only appear with the form of $r_{i} + 210 k$ , where $r_{i} \in S$ and $k \in N_{0}$ , since the rest is divisible by 2, 3, 5 or 7. So we only need to consider the primality of those numbers.

Furthermore, in our PTP method to list primes in the following observations, the cyclic behavior of the Factor-Pair Table with generation information is observed and utilized to ease computation burden.

3.1. Basic Binary Matrices

According to the 4th property of the Factor-Pair Table with generation information, we know

$\begin{matrix} t_{j | i} + r_{j} \leq 2 r_{j} \end{matrix}$ . (10)

To represent the generation information of each factor pair more clearly, we convert each column of the Factor-Pair Table with generation information, $V_{j}$ , into a basic binary matrix of composites $B_{j}^{o} = {[b_{j}^{0} (i, k)]}_{48 \times 2 r_{j}}$ for $i = 1, 2, \dots, 48$ , $k = 0, 1, 2, \dots, 2 r_{j} - 1$ , where $b_{j}^{0} (i, k) \in {0, 1}$ . In this matrix, $b_{j}^{0} (i, k) = 1$ indicates that the $k^{th}$ descendant of $r_{i}$ is a composite with a factor being $q_{j}$ .

Specifically, we specify $b_{j}^{0} (i, k)$ following the rule below:

The entry $b_{j}^{0} (i, k)$ is set as 1 only under two cases:

Case 1 ( $i = j$ ): if $k = r_{i}$ or $k = 0$ , $b_{j}^{0} (i, k) = 1$ .

Case 2 ( $i \neq j$ ): if $k = t_{j | i}$ or $k = t_{j | i} + r_{j}$ , $b_{j}^{0} (i, k) = 1$ .

Otherwise, $b_{j}^{0} (i, k) = 0$ .

Inequality (10) guarantees that the rule is properly defined.

Figure 1. Converting $V_{1}$ to $B_{1}^{0}$ .

We observe the following properties in $B_{j}^{0}$ :

1) There are exactly two non-zero entries for each $i$ , which means either Case 1 or Case 2 always sets two entries in $B_{j}^{0}$ as 1.

2) Every matrix $B_{j}^{0}$ consists of two identical submatrices of the size $48 \times r_{j}$ placed side by side.

3) Each non-zero entry in the submatrix mentioned in (2) corresponds to a factor-pair $(q_{j}, q_{\hat{j} | i})$ , $i = 1, 2, \dots, 48$ with its generation $t_{j | i}$ .

Figure 1 shows how to convert $V_{1}$ to $B_{1}^{0}$ . For instance,

we set $b_{1}^{0} (1, 0) = b_{1}^{0} (1, 11) = 1$ , moreover,

since $t_{1 | 2} = 9, b_{1}^{0} (2, 9) = b_{1}^{0} (2, 20) = 1$ ;

since $t_{1 | 3} = 5, b_{1}^{0} (3, 5) = b_{1}^{0} (3, 16) = 1$ ;

since $t_{1 | 4} = 3, b_{1}^{0} (4, 3) = b_{1}^{0} (4, 14) = 1$ .

Similarly, $V_{2}, V_{3}, \dots$ and $V_{48}$ is respectively converted into $B_{2}^{0}, B_{3}^{0}, \dots$ and $B_{48}^{0}$ .

3.2. Mapping Effect and Refined Binary Matrices

From Sections 2.1 and 2.2, we know a composite without factors of 2, 3, 5 and 7, which is rooted as $r_{i}$ , can be expressed as $α = r_{i} + 210 k = (q_{j} + 210 θ) \times (q_{\hat{j} | i} + 210 \hat{θ})$ , and its generation is

$t_{j | i} = \frac{q_{j} q_{\hat{j} | i} - r_{i}}{210} \in N_{0}$ .

Now if $θ = 0$ , we observe that for $k = t_{j | i} + q_{j} \times \hat{θ}$ , where $\hat{θ} \in N_{0}$ , $r_{i} + 210 t_{j | i}$ , $r_{i} + 210 (t_{j | i} + q_{j})$ , $r_{i} + 210 (t_{j | i} + 2 q_{j})$ , $r_{i} + 210 (t_{j | i} + 3 q_{j}), \dots$ , are all composites rooted at $r_{i}$ . That means, there is a mapping effect between $r_{i} + 210 t_{j | i}$ and $r_{i} + 210 (t_{j | i} + m \times q_{j})$ for any $m \in N_{+}$ .

Similarly, if $\hat{θ} = 0$ , there is a mapping effect between $r_{i} + 210 t_{j | i}$ and $r_{i} + 210 (t_{j | i} + m^{'} \times q_{\hat{j} | i})$ for $m^{'} \in N_{+}$ . Such an effect is very useful to quickly find the same-root composites based on the basic-binary-matrices, as described below:

Consider an integer interval from $11 + 210 \times k^{*}$ to $211 + 210 \times (k^{*} + δ)$ , where $k^{*} \in N_{+}$ , $δ \in N_{0}$ , $δ \leq 10 (< r_{1} = 11)$ . Define $B_{j} = {[b_{j} (i, k^{*} + h)]}_{48 \times (δ + 1)}$ , where $b_{j} (i, k^{*} + h) \in {0, 1}$ , as a refined binary matrix of composites for $i \in {1, 2, \dots, 48}$ , $h \in {0, 1, \dots, δ}$ . In other words, if $b_{j} (i, k) = 1$ , then the integer $r_{i} + 210 k$ is a composite number. But if $b_{j} (i, k) = 0$ , we can’t determine whether $r_{i} + 210 k$ is a prime, as discussed later. Theorem 5 then shows the mapping effect from $B_{j}^{0}$ to $B_{j}$ :

Theorem 5. If $k = w_{j} + r_{j} \times M$ , where $M \in N_{0}$ and $w_{j} \in {0, 1, \dots, 2 r_{j} - 1}$ , then for any $i \in {1, 2, \dots, 48}$ , if $b_{j}^{0} (i, w_{j}) = 1$ , then $r_{i} + 210 k$ is composite, i.e., $b_{j} (i, k) = 1$ .

The value of each entry is determined accordingly. By setting $w_{j} = k^{*} - r_{j} ⌊ k^{*} / r_{j} ⌋$ , we notice that $w_{j} + h \in {0, 1, \dots, 2 r_{j} - 1}$ . For any $h \in {0, 1, \dots, δ}$ and $i \in {1, 2, \dots, 48}$ , if $b_{j}^{0} (i, w_{j} + h) = 1$ , then set $b_{j} (i, k^{*} + h) = 1$ ; if $b_{j}^{0} (i, w_{j} + h) = 0$ , then set $b_{j} (i, k^{*} + h) = 0$ .

$B_{j}$ has the following properties:

1) $B_{j}$ is a submatrix of $B_{j}^{0}$ , with dimensionality of $48 \times (δ + 1)$ .

2) Each non-zero entry in $B_{j}$ corresponds to a composite number in the pre-specified interval.

The refined binary matrix $B_{j}$ can quickly locate large composites in a pre-specified interval. However, it’s not guaranteed that when $b_{j} (i, k^{*} + h) = 0$ , the corresponding integer is prime. The reason is that the mapping effect only locates composites with the form of $r_{i} + 210 (t_{j | i} + m \times q_{j}) = q_{j} \times (q_{\hat{j} | i} + 210 m)$ and $r_{i} + 210 (t_{j | i} + m^{'} \times q_{\hat{j} | i}) = q_{\hat{j} | i} \times (q_{j} + 210 m^{'})$ . For composites with the smallest factor larger than 211, $B_{j}$ may fail to detect them.

3.3. Composite Binary Matrix

A composite binary matrix $C = {[c (i, k)]}_{48 \times (δ + 1)}$ , where $i \in {1, 2, \dots, 48}$ and $k \in {k^{*}, k^{*} + 1, \dots, k^{*} + δ}$ , can be formed based on $B_{1}, B_{2}, \dots, B_{48}$ . We want to assure that all composites within the interval $[11 + 210 \times k^{*}, 211 + 210 \times (k^{*} + δ)]$ are detected and located by $C$ .

We first locate composite numbers detected by mapping effect. If $b_{j} (i, k) = 1$ for some $j \in {1, 2, \dots, 48}$ , the number $r_{i} + 210 k$ is a composite, i.e., $c (i, k) = 1$ . After that, we only need to determine the primality of the remaining numbers.

The specific algorithm is as follows:

Algorithm 2:

Step 1: For each $c (i, k)$ , where $i \in {1, 2, \dots, 48}$ and $k \in {k^{*}, k^{*} + 1, \dots, k^{*} + δ}$ , check $b_{j} (i, k)$ for $j \in {1, 2, \dots, 48}$ :

If $b_{j} (i, k) = 1$ for some $j$ , then set $c (i, k) = 1;$

otherwise, go to Step 2.

Step 2: Let $α = r_{i} + 210 k$ . Conduct a selected primality test algorithm for $α$ :

If $α$ is not a prime, set $c (i, k) = 1$ ;

otherwise, set $c (i, k) = 0$ .

With matrix $C$ , we can locate all composite numbers within the interval:

Theorem 6. In a prespecified interval $[11 + 210 \times k^{*}, 211 + 210 \times (k^{*} + δ)]$ , where $k^{*} \in N_{+}$ , $δ \in {[0, 10]}_{N}$ , any integer number $r_{i} + 210 k$ is composite if and only if $c (i, k) = 1$ .

3.4. Prime Binary Matrix

We are now able to form a binary matrix of primes $P = {[p (i, k)]}_{48 \times (δ + 1)}$ , where $i \in {1, 2, \dots, 48}$ and $k \in {k^{*}, k^{*} + 1, \dots, k^{*} + δ}$ , within the pre-specified interval. Each entry of $P$ is determined by $p (i, k) = 1 - c (i, k)$ , $i = 1, 2, \dots, 48$ and $k = k^{*}, k^{*} + 1, \dots, k^{*} + δ$ .

In this way, we can list all primes within the interval as illustrated in the following theorem:

Figure 2. An outline of observations.

Theorem 7. In a pre-specified interval $[11 + 210 \times k^{*}, 211 + 210 \times (k^{*} + δ)]$ , where $k^{*} \in N_{+}$ , $δ \in {[0, 10]}_{N}$ , any integer number $r_{i} + 210 k$ is prime if and only if $p (i, k) = 1$ .

Figure 2 is an outline of our PTP method for listing all primes within the interval $[11 + 210 \times k^{*}, 211 + 210 \times (k^{*} + δ)]$ for $δ \in {[0, 10]}_{N}$ .

We first form a $48 \times 48$ Factor-Pair Table with generation information, then convert each column of it into a basic binary matrix $B_{j}^{0}$ . After that, $B_{j}^{0}$ is modified as a refined binary matrix $B_{j}$ . By aggregating $B_{1}, B_{2}, \dots, B_{48}$ , and testing the primality of the rest numbers, we obtain a composite binary matrix $C$ . Based on $C = {[c (i, k)]}_{48 \times (δ + 1)}$ , we have a prime binary matrix $P = {[p (i, k)]}_{48 \times (δ + 1)}$ . The primes within the interval are listed as $α = r_{i} + 210 k$ for $k \in {k^{*}, k^{*} + 1, \dots, k^{*} + δ}$ such that $p (i, k) = 1$ in the prime binary matrix $P$ .

Moreover, all composites (without factors of 2, 3, 5 and 7) within the same interval can be predicted. Both primes and composites are illustrated on a PTP table.

4. Results

4.1. Formula of Primes

From Theorem 7, we have the following Formula of Primes:

Formula of Primes. All prime numbers within an integer interval $[11 + 210 \times k^{*}, 211 + 210 \times (k^{*} + δ)]$ , where $k^{*} \in N_{+}$ , $δ \in {[0, 10]}_{N}$ , have the form of $α = r_{i} + 210 k$ , where $k \in {k^{*}, k^{*} + 1, \dots, k^{*} + δ}$ and $i \in {1, 2, \dots, 48}$ , such that $p (i, k) = 1$ in the prime binary matrix $P$ .

4.2. Algorithm of Prime Listing

Finally, an algorithm for listing all primes in a pre-specified interval is presented below.

Algorithm 3:

Part A: Data Preparation

Firstly, we need to construct a $48 \times 48$ Factor-Pair Table with generation information, $(V_{1}, V_{2}, \dots, V_{48})$ . Then we can convert each $V_{j}$ into a basic binary matrix $B_{j}^{0} = {(b_{j}^{0} (i, k))}_{48 \times 2 r_{j}}$ , for $i = 1, 2, \dots, 48$ and $k = 0, 1, 2, \dots, 2 r_{j} - 1$ .

Part B: Prime Prediction (Given $k^{*} \in N_{+}$ , $δ \in {[0, 10]}_{N}$ )

Step 1: Generate refined binary matrices $B_{j} = {(b_{j} (i, k))}_{48 \times (δ + 1)}$ for $j = 1, 2, \dots, 48$ based on $B_{j}^{0}$ .

Step 2: Generate a composite binary matrix $C = {(c (i, k))}_{48 \times (δ + 1)}$ with Algorithm 2.

Step 3: Generate a prime binary matrix $P = {(p (i, k))}_{48 \times (δ + 1)}$ based on $C$ .

Step 4: The prime numbers within the interval $[11 + 210 \times k^{*}, 211 + 210 \times (k^{*} + δ)]$ can be listed as

${α = r_{i} + 210 k | p (i, k) = 1, i = 1, 2, \dots, 48, k = k^{*}, k^{*} + 1, \dots, k^{*} + δ}$ .

In the above algorithm, Part A and Step 1, Step 3 and Step 4 in Part B require constant time complexity. Step 2 in Part B involves a few primality tests, whose complexity can be reduced by choosing a more efficient primality test algorithm.

An example of Algorithm 3 can be found in Appendix A.

The procedure of Part B is presented in Figure 3. The top row shows $B_{1}, B_{2}, \dots, B_{48}, C$ and $P$ , respectively. The second row is for $k^{*} = 924$ , $k^{*} + 1 = 925$ and $k^{*} + 2 = 926$ . The third row is for $(δ_{j}, δ_{j} + 1, δ_{j} + 2)$ , where $j = 1, 2, \dots, 48$ . The $b_{j} (i, k)$ entry denotes the binary value for given $B_{j}, r_{i}$ and $k$ .

A table of listing all primes in $[11 + 210 \times 922, 211 + 210 \times 928]$ is shown in Table 2.

Figure 3. Process of predicting primes in [11 + 210 × 924, 211 + 210 × 926].

Table 2. Prediction of Primes within [11 + 210 × 922, 211 + 210 × 928].

		924	925	926
1	11			194,471
2	13		194,263
3	17	194,057	194,267
4	19		194,269	194,479
5	23			194,483
6	29	194,069
7	31	194,071
8	37
9	41
10	43	194,083
11	47	194,087		194,507
12	53	194,093
13	59		194,309
14	61	194,101		194,521
15	67			194,527
16	71
17	73	194,113	194,323
18	79	194,119
19	83			194,543
20	89
21	97
22	101	194,141
23	103		194,353
24	107
25	109	194,149		194,569
26	113
27	121		194,371	194,581
28	127	194,167	194,377
29	131			194,591
30	137
31	139	194,179
32	143
33	149			194,609
34	151
35	157	194,197
36	163	194,203	194,413
37	167
38	169
39	173
40	179
41	181		194,431
42	187			194,647
43	191
44	193		194,443	194,653
45	197
46	199	194,239		194,659
47	209
48	211			194,671

4.3. The Periodic Table of Primes

The Periodic Table of Primes (PTP) is shown in Figure 4. Reconstructed from our prime listing algorithm, it illustrates that composites (without factors of 2, 3, 5 and 7) are distributed cyclically and primes are distributed periodically.

Figure 4. PTP [11, 211 + 210²].

5. Discussion

In this paper, we propose a novel way to list primes. Given an interval, without loss of generality, we first restrict the range of numbers to those having the form of $α = r_{i} + 210 k$ . Then, by mapping the effect, we further eliminate a good amount of numbers and conduct primality checking on the rest of the numbers. Subsequently, we list all primes in the given interval.

Some further discussions are as follows:

1) With theoretical analysis and computer validation (in Appendix B), we can, on average, identify about 26 composite numbers in a column. This demonstrates that the proposed method largely reduces the number of primality checks required in the prime listing task over a pre-specified interval with simple mappings. The details are found in Appendix B.

2) In practice, we can use bitwise operations to speed up the algorithm. We first encode each column of the basic binary matrices into a binary number, and the same applies to the columns of the refined binary matrices. Then, instead of checking individual entries, we perform the bitwise operation “OR” on all columns in the refined binary matrix corresponding to a certain column. With a significant improvement in efficiency, the resulting value implies the composites located in this column by Step 1 of Algorithm 2.

3) In this paper and all associated demonstrations, we consider composites without factors of 2, 3, 5 and 7 to generate a Factor-Pair Table which gives way to a designated and graphics-manageable period of $2 \times 3 \times 5 \times 7 = 210$ . To improve efficiency and to list a larger number of primes, we may consider composites without factors of 2, 3, 5, 7 and 11 which represent a larger period of $2 \times 3 \times 5 \times 7 \times 11 = 2310$ . Further extension is also possible for even larger dimension by adding primes 13, 17, …

4) The proposed algorithm is obviously capable of listing prime numbers within a specific interval starting from a very large number. Unlike the conventional methods, the proposed algorithm does not require prior knowledge of smaller prime numbers. Furthermore, the mapping process has constant time and small space complexity, ensuring high efficiency.

5) We are investigating the application of the proposed method in various domains, such as cryptography-security, hash-data-base-design and DNA-sequence-identify.

Appendix A: An Example of Algorithm 3

Example: (List all primes within the interval $[11 + 210 \times 924, 211 + 210 \times 926]$ )

Part A:

The Factor-Pair Table with generation information is shown in Table 1 and the basic binary matrices $B_{j}^{0}$ , $j = 1, 2, \dots, 48$ , are converted accordingly.

Part B:

Step 1: Generate refined binary matrices $B_{j} = {(b_{j} (i, k))}_{48 \times 3}$ for $j = 1, 2, \dots, 48$ based on $B_{j}^{0}$ .

Take $j = 1$ for example, $B_{1} = {(b_{1} (i, k))}_{48 \times 3}$ , where $i = 1, 2, \dots, 48$ and $k = 924, 925, 926$ , and $w_{1} = 924 - 11 \times ⌊ 924 / 11 ⌋ = 0$ . From Theorem 5, $b_{1} (i, 924 + h) = b_{1}^{0} (i, w_{1} + h) = b_{1}^{0} (i, h)$ . From $B_{1}^{0}$ in Figure 1, we know that

$∵ b_{1}^{0} (1, 0) = b_{1}^{0} (27, 0) = b_{1}^{0} (32, 0) = b_{1}^{0} (42, 0) = b_{1}^{0} (47, 0) = 1$ ,

$∴ b_{1} (1, 924) = b_{1} (27, 924) = b_{1} (32, 924) = b_{1} (42, 924) = b_{1} (47, 924) = 1$ .

Similarly,

$∵ b_{1}^{0} (10, 1) = b_{1}^{0} (25, 1) = b_{1}^{0} (29, 1) = b_{1}^{0} (45, 1) = 1$ ,

$∴ b_{1} (10, 925) = b_{1} (25, 925) = b_{1} (29, 925) = b_{1} (45, 925) = 1$ .

$∵ b_{1}^{0} (7, 2) = b_{1}^{0} (12, 2) = b_{1}^{0} (21, 2) = b_{1}^{0} (36, 2) = 1$ ,

$∴ b_{1} (7, 926) = b_{1} (12, 926) = b_{1} (21, 926) = b_{1} (36, 926) = 1$ .

Step 2: Generate a composite binary matrix $C = {(c (i, k))}_{48 \times 3}$ with Algorithm 2.

Check $b_{j} (i, k)$ for all $j \in {1, 2, \dots, 48}$ , $i \in {1, 2, \dots, 48}$ and $k \in {924, 925, 926}$ .

For $i \in {1, 2, 4, 5, 13, 15, 19, 20, 21, 23, 24, 26, 27, 32, 33, 34, 38, 39, 41, 42, 43, 44, 45,$ $47}$ , set $c (i, 924) = 1$ ;

for other $i$ , we run primality test and set $c (i, 924) = 1$ for $i \in {8, 9, 16, 29, 30, 37, 40, 48}$ .

For $i \in {3, 6, 7, 10, 11, 12, 14, 17, 18, 22, 25, 28, 31, 35, 36, 46}$ , set $c (i, 924) = 0$ .

For $i \in {1, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 22, 26, 29, 30, 31, 33, 34, 35, 38, 39, 40,$ $42, 43, 45, 47}$ , set $c (i, 925) = 1$ ;

for other $i$ , we run primality test and set $c (i, 925) = 1$ for $i \in {11, 16, 19, 24, 25, 32, 37, 46, 48}$ .

For $i \in {2, 3, 4, 13, 17, 23, 27, 28, 36, 41, 44}$ , set $c (i, 925) = 0$ .

For $i \in {2, 6, 7, 8, 9, 10, 12, 13, 16, 17, 21, 22, 23, 24, 26, 28, 30, 31, 32, 34, 35, 36, 37,$ $38, 39, 40, 41, 43, 47}$ , set $c (i, 926) = 1$ ;

for other $i$ , we run primality test and set $c (i, 926) = 1$ for $i \in {3, 18, 20, 45}$ .

For $i \in {1, 4, 5, 11, 14, 15, 19, 25, 27, 29, 33, 42, 44, 46, 48}$ , set $c (i, 926) = 0$ .

Step 3: Generate a prime binary matrix $P = {(p (i, k))}_{48 \times 3}$ based on $C$ .

For $i \in {1, 2, \dots, 48}$ and $k \in {924, 925, 926}$ , set $p (i, k) = 1 - c (i, k)$ .

Step 4: The prime numbers within the interval $[11 + 210 \times 924, 211 + 210 \times 926]$ can be listed as

$\begin{array}{l} {α = r_{i} + 210 k | p (i, k) = 1, i = 1, 2, \dots, 48, k = 924, 925, 926} \\ = {194471, 194263, 194057, 194267, 194269, 194479, 194483, 194069, 194071, \\ 194083, 194087, 194507, 194093, 194309, 194101, 194521, 194527, 194113, \\ 194323, 194119, 194543, 194141, 194353, 194149, 194569, 194371, 194581, \\ 194167, 194377, 194591, 194179, 194609, 194197, 194203, 194413, 194431, \\ 194647, 194443, 194653, 194239, 194659, 194671} \end{array}$

Appendix B: Theoretical Analysis and Computer Validation of Algorithm 2

The formulation of the Composite Binary Matrix $C$ is the most vital step in our proposed prime listing algorithm, and Step 1 in Algorithm 2 locates a good portion of composites in a pre-specified interval with constant time complexity. In the following analysis, we will conduct a comprehensive computation to see the expectation of the composites located in a column by Step 1. It is more reasonable to count all composites within the period than to analyze the performance of each column, as the latter is too time-consuming to study.

After conducting Step 1, the entries of column $c (i, k^{*})$ are either 1 or 0. If $c (i, k_{1}) - c (i, k_{2}) = 0$ for $i \in {1, 2, \dots, 48}$ , we call the “result” of columns $k_{1}$ and $k_{2}$ identical. To analyze the effect of Step 1, we first elaborate that the “results” of Step 1 appear cyclically in the columns.

Theorem 5 implies that in a certain column $k$ of matrix $C$ , at which the entries are located as composite by Step 1 is determined by the result of

$\begin{matrix} w_{1} = k - r_{1} \frac{k^{*}}{r_{1}}, w_{2} = k - r_{2} \frac{k^{*}}{r_{2}}, \dots, w_{48} = k - r_{48} \frac{k^{*}}{r_{48}} \end{matrix}$ , (11)

which is identical to

$\begin{matrix} k \equiv w_{j} (mod r_{j}), w_{j} \in {0, 1, \dots, r_{j} - 1}, j \in {1, 2, \dots, 48} \end{matrix}$ (12)

in modular arithmetic. If there exists $j$ such that $b_{j}^{0} (i, w_{j}) = 1$ , then $b_{j} (i, k) = 1$ , $c (i, k) = 1$ and $r_{i} + 210 \times k$ is a composite number.

We claim that there are infinite $k$ ’s satisfying Equation (11) and they are of the same cyclic form. Denoting L as the least common multiple of $r_{1}, r_{2}, \dots, r_{48}$ , we have L = 1, 120, 700, 227, 446, 262, 311, 648, 514, 688, 739, 473, 686, 196, 699, 653, 055, 999, 250, 791, 866, 994, 591, 464, 755, 146, 178, 654, 953. Given $w_{1}, w_{2}, \dots, w_{48}$ , the Chinese Remainder Theorem says that there’s a unique solution $k^{*}$ , if any, in ${[1, L]}_{N}$ for Equation (11) and the general solution can be expressed as $k^{*} + L \times t$ , where $t \in N_{0}$ .

With the cyclic behavior detected, we can now limit our attention to the case where $k \in {[1, L]}_{N}$ . However, the period L is too large to be counted directly, so we need some further analysis.

We should notice that for any $i \in {1, 2, \dots, 48}$ , there’s one and only one $w_{j}$ in ${0, 1, \dots, r_{j} - 1}$ such that $b_{j}^{0} (i, w_{j}) = 1$ , indicating $r_{i} + 210 \times k$ is composite. We denote this $w_{j}$ as $d_{i j}$ in the following discussion.

To avoid duplicated computation induced by the 5 composite numbers in $S$ , we divide the set $S$ into $S_{1} = {11, 13, 143, 187, 209}$ , $S_{2} = {17, 19, 121, 169}$ and $S_{3} = S \ (S_{1} \cup S_{2})$ . Accordingly, the index set $I = {1, 2, \dots, 48}$ is divided into $I_{1} = {1, 2, 32, 42, 47}$ , $I_{2} = {3, 4, 27, 38}$ and $I_{3} = I \ (I_{1} \cup I_{2})$ .

The following Corollary demonstrates that ${w_{j} | j \in I_{2} \cup I_{3}}$ can uniquely determine a solution in ${[1, L]}_{N}$ for Equation (11). The reason is that ${w_{j} | j \in I_{1}}$ can be directly calculated given ${w_{j} | j \in I_{2}}$ .

Corollary of the Chinese Remainder Theorem. Given $w_{1}, w_{2}, \dots, w_{48}$ , Equation (11) has a solution in ${[1, L]}_{N}$ if and only if

$\begin{matrix} {\begin{array}{l} w_{1} \equiv w_{27} (mod 11) \\ w_{2} \equiv w_{38} (mod 13) \\ w_{32} \equiv 78 w_{1} + 66 w_{2} (mod 143) \\ w_{42} \equiv 34 w_{1} + 154 w_{3} (mod 187) \\ w_{47} \equiv 133 w_{1} + 77 w_{4} (mod 209) \end{array} \end{matrix}$ (13)

and

$\begin{matrix} k \equiv w_{j} (mod r_{j}), w_{j} \in {0, 1, \dots, r_{j} - 1}, j \in I_{2} \cup I_{3} \end{matrix}$ (14)

has a solution in ${[1, L]}_{N}$ .

The above Corollary is derived from the Chinese Remainder Theorem and can be easily verified. With this theorem, we can count how many composites are located by Step 1 in columns 1 to $L$ .

Without loss of generality, we first focus on $i = 1$ .

Since each column in ${[1, L]}_{N}$ can be uniquely determined by ${w_{j} | j \in I_{2} \cup I_{3}}$ , we first consider ${w_{j} | j \in I_{2}} = {w_{3}, w_{4}, w_{27}, w_{38}}$ . Notice that ${w_{j} | j \in I_{1}}$ is determined by Equation (13) for any fixed ${w_{j} | j \in I_{2}}$ .

If there exists at least a $j \in I_{2}$ such that $w_{j} = d_{1 j}$ , then $r_{i} + 210 \times k$ is a composite number no matter the value of $w_{j}$ , $j \in I_{3}$ . The number of ${w_{3}, w_{4}, w_{27}, w_{38}}$ satisfying this case is $r_{3} r_{4} r_{27} r_{38} - (r_{3} - 1) (r_{4} - 1) (r_{27} - 1) (r_{38} - 1) = 798947$ . In this case, $w_{j}, j \in I_{3}$ can be chosen arbitrarily from the domain. Therefore, there are $\prod_{j \in I_{3}} r_{j}$ composites located for each such ${w_{3}, w_{4}, w_{27}, w_{38}}$ in ${[1, L]}_{N}$ .

If $w_{j} \neq d_{1 j}$ for any $j \in I_{2}$ but there exists at least a $j \in I_{1}$ such that $w_{j} = d_{1 j}$ , there are also $\prod_{j \in I_{3}} r_{j}$ composites located for each such ${w_{3}, w_{4}, w_{27}, w_{38}}$ . Here $w_{j}, j \in I_{1}$ is computed by Equation (13). The number of ${w_{3}, w_{4}, w_{27}, w_{38}}$ satisfying this case is 864000 (Counted by computer, this value is the same when $i = 2, 3, \dots, 48$ ).

If $w_{j} \neq d_{1 j}$ for any $j \in I_{1} \cup I_{2}$ , then a composite number is located if and only if there exists $w_{j} = d_{1 j}$ for some $j \in I_{3}$ . Therefore, there are $\prod_{j \in I_{3}} r_{j} - \prod_{j \in I_{3}} (r_{j} - 1)$ composites located in ${[1, L]}_{N}$ for each such ${w_{3}, w_{4}, w_{27}, w_{38}}$ . The number of ${w_{3}, w_{4}, w_{27}, w_{38}}$ satisfying this case is 4942080.

When $i = 2, 3, \dots, 48$ , the number of composites located by Step 1 in columns ${[1, L]}_{N}$ is the same as $i = 1$ . Since

$\begin{matrix} \prod_{j \in I_{3}} r_{j} = 169, 673, 829, 864, 171, 987, 737, 296, 863, 243, 628, 479, 671, 120, 141, 228, \\ 188, 658, 546, 265, 896, 353, 105, 711, 020, 739 \end{matrix}$

and

$\begin{matrix} \prod_{j \in I_{3}} (r_{j} - 1) = 102, 585, 912, 060, 381, 157, 597, 756, 546, 764, 390, 409, 686, 966, 581, \\ 524, 267, 485, 974, 696, 558, 592, 000, 000, 000, 000, \end{matrix}$

the total number of composites located by Step 1 in columns ${[1, L]}_{N}$ is

$\begin{matrix} T = 48 \times [798947 \prod_{j \in I_{3}} r_{j} + 864000 \prod_{j \in I_{3}} r_{j} + 4942080 (\prod_{j \in I_{3}} r_{j} - \prod_{j \in I_{3}} (r_{j} - 1))) \\ = 29, 458, 197, 272, 202, 902, 414, 774, 112, 677, 093, 526, 253, 964, 920, \\ 792, 154, 274, 897, 889, 854, 062, 645, 442, 967, 016, 575, 437, 744 \end{matrix}$

The average number of composites located by Step 1 in a PTP’s column is $T / L = 26.285528057158732$ in the first period ${[1, L]}_{N}$ and can be regarded as the overall expectation of the number of composites located by Step 1 in a PTP’s column, which is over $26.28 / 48 = 54.75 %$ of the numbers in the column.

To further validate this result, the number of composites located by Step 1 in PTP’s columns 1 to 10¹² is on average 26.285525173295, which is quite close to our theoretical result.

The theoretical analysis and numerical experiment above illustrate that the proposed method largely reduces the number of primality checks in the prime listing task over a pre-specified interval.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Li, H., Fang, S. and Kuo, W. (2024) The Periodic Table of Primes. Advances in Pure Mathematics, 14, 394-419.[CrossRef]
[2]	Bach, E. and Shallit, J. (1996) Algorithmic Number Theory. MIT Press.
[3]	O’Neill, M.E. (2009) The Genuine Sieve of Eratosthenes. Journal of Functional Programming, 19, 95-106.[CrossRef]
[4]	Dijkstra, E.W. (1972) Notes on Structured Programming. In: Dijkstra, E.W., Dahl, O.J. and Hoare, C.A.R., Eds., Structured Programming, Academic Press Ltd., 1-82.
[5]	Atkin, A.O.L. and Bernstein, D.J. (2003) Prime Sieves Using Binary Quadratic Forms. Mathematics of Computation, 73, 1023-1030.[CrossRef]
[6]	Pritchard, P. (1983) Fast Compact Prime Number Sieves (among Others). Journal of Algorithms, 4, 332-344. [Google Scholar] [CrossRef]
[7]	Helfgott, H.A. (2019) An Improved Sieve of Eratosthenes. Mathematics of Computation, 89, 333-350.[CrossRef]
[8]	Pritchard, P. (1982) Explaining the Wheel Sieve. Acta Informatica, 17, 477-485.[CrossRef]
[9]	Agrawal, M., Kayal, N. and Saxena, N. (2004) PRIMES Is in P. Annals of Mathematics, 160, 781-793.[CrossRef]
[10]	Miller, G.L. (1975) Riemann’s Hypothesis and Tests for Primality. Proceedings of Seventh Annual ACM Symposium on Theory of Computing, Albuquerque, 5-7 May 1975, 234-239.[CrossRef]
[11]	Rabin, M.O. (1980) Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12, 128-138.[CrossRef]

	[email protected]
	+86 18163351462 (WhatsApp)
	1655362766
	SCIRP WeChat

Journals Menu

Home

About SCIRP

Service

Policies