Judging prime numbers

Prime Number Algorithm

Prime numbers are very important in computer science. In the famous RSA protocol, it is done by factoring large integers. Its difficulty determines the reliability of the RSA algorithm.

In Goldbach's conjecture, the calculation of prime numbers is also very important. In future section, we will study how to prove Goldbach's conjecture on finite sets.

what is prime number

The opposite of prime numbers is composite numbers.

A prime number refers to a number that is factored. If the factor is only 1 and itself, then the number is a prime number.

For example, the smallest prime number and the only even prime number is 2, because 2=1*2, only 1 and itself are factors.

Then 3 and 5 and 7 and 11 are also prime numbers.

We see 4=2*2, so 4 is a sum, then there are 6, 8, 9, 10, 12 and so on.

According to the above method, it is easy to write a program to calculate the prime numbers:

first try

In the first attempt we didn't consider efficiency, we just wrote a program that would work.

def prime_detect_v1(num):
    for i in range(2, num):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

for i in range(2, 20):
    print(i, end='\t')
    print(prime_detect_v1(i))

The program is very simple. If a number is not divisible by all numbers less than itself, then the number is a prime number, otherwise a composite number.

2	prime number
3	prime number
4	composite number
5	prime number
6	composite number
7	prime number
8	composite number
9	composite number
10	composite number
11	prime number
12	composite number
13	prime number
14	composite number
15	composite number
16	composite number
17	prime number
18	composite number
19	prime number
>>> 

We simply run it and the program is correct.

second attempt

In the first attempt we only considered correctness, this version we consider efficiency:

The most time-consuming thing in determining prime function is the loop. If we can reduce the number of loops, then the efficiency of our program can increase.

If there is a number 29, and we want to determine whether it is a prime number or not, do we need to try from 2 all the way to 28? No, because if numbers up to (square 29)+1 are not divisible by 29, then neither can numbers over (square 29)+1.

def prime_detect_v1(num):
    for i in range(2, num):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

import math

def prime_detect_v2(num):
    for i in range( 2, int(math.sqrt(num))+1 ):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

for i in range(2, 30):
    print(i, end='\t')
    # print(prime_detect_v1(i))
    print(prime_detect_v2(i))

2	prime number
3	prime number
4	composite number
5	prime number
6	composite number
7	prime number
8	composite number
9	composite number
10	composite number
11	prime number
12	composite number
13	prime number
14	composite number
15	composite number
16	composite number
17	prime number
18	composite number
19	prime number
20	composite number
21	composite number
22	composite number
23	prime number
24	composite number
25	composite number
26	composite number
27	composite number
28	composite number
29	prime number
>>> 

Such a method reduces a considerable amount of computation.

third attempt

The second attempt reduced the computational load by a considerable amount, so can we go further?

YES!

We know that all even numbers except 2 are not prime numbers, so it is very simple, we can exclude all even numbers except 2.

def prime_detect_v1(num):
    for i in range(2, num):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

import math

def prime_detect_v2(num):
    for i in range( 2, int(math.sqrt(num))+1 ):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

def prime_detect_v3(num):
    if num == 2:
        return 'prime number'
    if num % 2 == 0:
        return 'composite number'
    for i in range( 3, int(math.sqrt(num))+1, 2 ):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

for i in range(2, 30):
    print(i, end='\t')
    # print(prime_detect_v1(i))
    # print(prime_detect_v2(i))
    print(prime_detect_v3(i))

2	prime number
3	prime number
4	composite number
5	prime number
6	composite number
7	prime number
8	composite number
9	composite number
10	composite number
11	prime number
12	composite number
13	prime number
14	composite number
15	composite number
16	composite number
17	prime number
18	composite number
19	prime number
20	composite number
21	composite number
22	composite number
23	prime number
24	composite number
25	composite number
26	composite number
27	composite number
28	composite number
29	prime number
>>> 

But since 2 is also the first number to be tested if you follow the normal process, this method does not change that much. Using this method reduces the amount of computation by about half.

fourth attempt

In the third attempt, we ruled out all multiples of 2, so can we do the same for multiples of 3? Of course it is possible.

Any natural number can always be expressed in one of the following six forms: 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5 (n=0,1,2...)

We can find that, apart from 2 and 3, only numbers of the form 6n+1 and 6n+5 can be prime numbers. And if numbers of the form 6n+1 and 6n+5 are not prime numbers, their factors will also contain numbers of the form 6n+1 or 6n+5, so the following algorithm can be obtained:

def prime_detect_v1(num):
    for i in range(2, num):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

import math

def prime_detect_v2(num):
    for i in range( 2, int(math.sqrt(num))+1 ):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

def prime_detect_v3(num):
    if num == 2:
        return 'prime number'
    if num % 2 == 0:
        return 'composite number'
    for i in range( 3, int(math.sqrt(num))+1, 2 ):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

def prime_detect_v4(num):
    if num == 2 or num == 3:
        return 'prime number'
    if num % 6 != 1 and num % 6 != 5:
        return 'composite number'
    for i in range( 5, int(math.sqrt(num))+1, 6 ):
        if num % i == 0 or num % (i + 2) == 0:
            return 'composite number'
    return 'prime number'

for i in range(2, 50):
    print(i, end='\t')
    # print(prime_detect_v1(i))
    # print(prime_detect_v2(i))
    # print(prime_detect_v3(i))
    print(prime_detect_v4(i))

2	prime number
3	prime number
4	composite number
5	prime number
6	composite number
7	prime number
8	composite number
9	composite number
10	composite number
11	prime number
12	composite number
13	prime number
14	composite number
15	composite number
16	composite number
17	prime number
18	composite number
19	prime number
20	composite number
21	composite number
22	composite number
23	prime number
24	composite number
25	composite number
26	composite number
27	composite number
28	composite number
29	prime number
30	composite number
31	prime number
32	composite number
33	composite number
34	composite number
35	composite number
36	composite number
37	prime number
38	composite number
39	composite number
40	composite number
41	prime number
42	composite number
43	prime number
44	composite number
45	composite number
46	composite number
47	prime number
48	composite number
49	composite number
>>> 

This approach has reached the limit of artificial optimization, so we will not use the same method to optimize this program (you can add 5 or 7 or 11 ... optimization algorithms, but these optimizations decrease marginally as the number increases, and the code changes is too complicated, so I will not continue to use this method to optimize)

fifth attempt

The previous algorithm has reached the limit of optimization, so if we want to continue to optimize the program, we can only change the algorithm.

There are three different measures of Labor complexity and space complexity and time complexity in the program.

Labor complexity refers to the labor cost of writing a program. The simpler the program, the lower the labor complexity, and vice versa.

We use python because the Labor complexity of python is very low, so many python programs do not care so much about the time complexity or space complexity, because in scientific research, most programs do not run many times, and the length of time to write code is long. Much larger than the running time, and writing the program quickly is the most important.

Space complexity refers to the memory and disk size occupied by a program. The larger the space complexity, the larger the disk and memory size occupied by the program.

Time complexity refers to the length of the running time of the program. In theory, we can calculate the time complexity of the program running (check algorithm books for details, and mathematics is not explained here). However, due to the multi-level cache mechanism of the computer and the connection mechanism of the memory, the time complexity is complicated. It is difficult to predict correctly (we are only predicting a trend), so the time complexity of a program is often calculated by running the program thousands of times (most programs run for a very short time, and the measured results are inaccurate) and measure the actual time divided by number of times the programming runs.

For a series of algorithms that are not stupid, the weighted product of Labor complexity and space complexity and time complexity is generally similar. That is to say, if the Labor complexity of an algorithm is relatively high, then the space complexity and time complexity of the algorithm will be relatively low.

In the previous program, the program became more and more complex, which is our Labor complexity has been increasing, but the corresponding time complexity has been decreasing.

Now our time complexity can't seem to be reduced, so we can convert some time complexity and Labor complexity into space complexity to reduce time complexity and Labor complexity.

Today's computers are more resourceful (not always running out of memory as in 1990) and many programs can mediate between these three complexities.

def prime_detect_v1(num):
    for i in range(2, num):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

import math

def prime_detect_v2(num):
    for i in range( 2, int(math.sqrt(num))+1 ):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

def prime_detect_v3(num):
    if num == 2:
        return 'prime number'
    if num % 2 == 0:
        return 'composite number'
    for i in range( 3, int(math.sqrt(num))+1, 2 ):
        if num % i == 0:
            return 'composite number'
    return 'prime number'

def prime_detect_v4(num):
    if num == 2 or num == 3:
        return 'prime number'
    if num % 6 != 1 and num % 6 != 5:
        return 'composite number'
    for i in range( 5, int(math.sqrt(num))+1, 6 ):
        if num % i == 0 or num % (i + 2) == 0:
            return 'composite number'
    return 'prime number'

import numpy as np
prime_list = np.array([2]) # init

def prime_detect_v5(num):
    global prime_list # passed to the function
    for i in prime_list[ prime_list < int(math.sqrt(num))+1 ]:
        if num % i == 0:
            return 'composite number'
    
    prime_list = np.append(prime_list, num)
    return 'prime number'

for i in range(2, 100):
    print(i, end='\t')
    # print(prime_detect_v1(i))
    # print(prime_detect_v2(i))
    # print(prime_detect_v3(i))
    # print(prime_detect_v4(i))
    print(prime_detect_v5(i))

In this method we build an array in which we keep all the prime numbers that have been tested.

Then we only need to divide the detected number by all the values in the array that are less than the square root of the detected number when we perform the detection.

This method has the same time complexity as the previous method, and the space complexity is much larger, but it is very easy to think of.

If a number is even, then the first number 2 in the array can rule out that the number is prime, and if a number is a multiple of 3, then the second number 3 in the array can rule out the number being prime.

The disadvantage of this method is that the continuous sequence must be detected, and in reality we generally only need to detect whether a certain number is a prime number. Which this method doesnot work.

2	prime number
3	prime number
4	composite number
5	prime number
6	composite number
7	prime number
8	composite number
9	composite number
10	composite number
11	prime number
12	composite number
13	prime number
14	composite number
15	composite number
16	composite number
17	prime number
18	composite number
19	prime number
20	composite number
21	composite number
22	composite number
23	prime number
24	composite number
25	composite number
26	composite number
27	composite number
28	composite number
29	prime number
30	composite number
31	prime number
32	composite number
33	composite number
34	composite number
35	composite number
36	composite number
37	prime number
38	composite number
39	composite number
40	composite number
41	prime number
42	composite number
43	prime number
44	composite number
45	composite number
46	composite number
47	prime number
48	composite number
49	composite number
50	composite number
51	composite number
52	composite number
53	prime number
54	composite number
55	composite number
56	composite number
57	composite number
58	composite number
59	prime number
60	composite number
61	prime number
62	composite number
63	composite number
64	composite number
65	composite number
66	composite number
67	prime number
68	composite number
69	composite number
70	composite number
71	prime number
72	composite number
73	prime number
74	composite number
75	composite number
76	composite number
77	composite number
78	composite number
79	prime number
80	composite number
81	composite number
82	composite number
83	prime number
84	composite number
85	composite number
86	composite number
87	composite number
88	composite number
89	prime number
90	composite number
91	composite number
92	composite number
93	composite number
94	composite number
95	composite number
96	composite number
97	prime number
98	composite number
99	composite number
>>> 

ensemble

We can put these methods together to see the correctness:

A basic way to check whether a program is right or wrong is a checker: use random numbers or a lot of data to check your method multiple times against a library function method (or two methods you write, one algorithm, the other is the brute force calculation) results are the same or not.

def prime_detect_v1(num):
    for i in range(2, num):
        if num % i == 0:
            return 'composite'
    return 'prime'

import math

def prime_detect_v2(num):
    for i in range( 2, int(math.sqrt(num))+1 ):
        if num % i == 0:
            return 'composite'
    return 'prime'

def prime_detect_v3(num):
    if num == 2:
        return 'prime'
    if num % 2 == 0:
        return 'composite'
    for i in range( 3, int(math.sqrt(num))+1, 2 ):
        if num % i == 0:
            return 'composite'
    return 'prime'

def prime_detect_v4(num):
    if num == 2 or num == 3:
        return 'prime'
    if num % 6 != 1 and num % 6 != 5:
        return 'composite'
    for i in range( 5, int(math.sqrt(num))+1, 6 ):
        if num % i == 0 or num % (i + 2) == 0:
            return 'composite'
    return 'prime'

import numpy as np
prime_list = np.array([2]) # init

def prime_detect_v5(num):
    global prime_list # passed to the function
    for i in prime_list[ prime_list < int(math.sqrt(num))+1 ]:
        if num % i == 0:
            return 'composite'
    
    prime_list = np.append(prime_list, num)
    return 'prime'

for i in range(2, 1000):
    print(i, end='\t')
    print(prime_detect_v1(i), end=' ')
    print(prime_detect_v2(i), end=' ')
    print(prime_detect_v3(i), end=' ')
    print(prime_detect_v4(i), end=' ')
    print(prime_detect_v5(i))

2	prime prime prime prime prime
3	prime prime prime prime prime
4	composite composite composite composite composite
5	prime prime prime prime prime
6	composite composite composite composite composite
7	prime prime prime prime prime
8	composite composite composite composite composite
9	composite composite composite composite composite
10	composite composite composite composite composite
11	prime prime prime prime prime
12	composite composite composite composite composite
13	prime prime prime prime prime
14	composite composite composite composite composite
15	composite composite composite composite composite
16	composite composite composite composite composite
17	prime prime prime prime prime
18	composite composite composite composite composite
19	prime prime prime prime prime
20	composite composite composite composite composite
21	composite composite composite composite composite
22	composite composite composite composite composite
23	prime prime prime prime prime
24	composite composite composite composite composite
25	composite composite composite composite composite
26	composite composite composite composite composite
27	composite composite composite composite composite
28	composite composite composite composite composite
29	prime prime prime prime prime
30	composite composite composite composite composite
31	prime prime prime prime prime
32	composite composite composite composite composite
33	composite composite composite composite composite
34	composite composite composite composite composite
35	composite composite composite composite composite
36	composite composite composite composite composite
37	prime prime prime prime prime
38	composite composite composite composite composite
39	composite composite composite composite composite
40	composite composite composite composite composite
41	prime prime prime prime prime
42	composite composite composite composite composite
43	prime prime prime prime prime
44	composite composite composite composite composite
45	composite composite composite composite composite
46	composite composite composite composite composite
47	prime prime prime prime prime
48	composite composite composite composite composite
49	composite composite composite composite composite
50	composite composite composite composite composite
51	composite composite composite composite composite
52	composite composite composite composite composite
53	prime prime prime prime prime
54	composite composite composite composite composite
55	composite composite composite composite composite
56	composite composite composite composite composite
57	composite composite composite composite composite
58	composite composite composite composite composite
59	prime prime prime prime prime
60	composite composite composite composite composite
61	prime prime prime prime prime
62	composite composite composite composite composite
63	composite composite composite composite composite
64	composite composite composite composite composite
65	composite composite composite composite composite
66	composite composite composite composite composite
67	prime prime prime prime prime
68	composite composite composite composite composite
69	composite composite composite composite composite
70	composite composite composite composite composite
71	prime prime prime prime prime
72	composite composite composite composite composite
73	prime prime prime prime prime
74	composite composite composite composite composite
75	composite composite composite composite composite
76	composite composite composite composite composite
77	composite composite composite composite composite
78	composite composite composite composite composite
79	prime prime prime prime prime
80	composite composite composite composite composite
81	composite composite composite composite composite
82	composite composite composite composite composite
83	prime prime prime prime prime
84	composite composite composite composite composite
85	composite composite composite composite composite
86	composite composite composite composite composite
87	composite composite composite composite composite
88	composite composite composite composite composite
89	prime prime prime prime prime
90	composite composite composite composite composite
91	composite composite composite composite composite
92	composite composite composite composite composite
93	composite composite composite composite composite
94	composite composite composite composite composite
95	composite composite composite composite composite
96	composite composite composite composite composite
97	prime prime prime prime prime
98	composite composite composite composite composite
99	composite composite composite composite composite
100	composite composite composite composite composite
101	prime prime prime prime prime
102	composite composite composite composite composite
103	prime prime prime prime prime
104	composite composite composite composite composite
105	composite composite composite composite composite
106	composite composite composite composite composite
107	prime prime prime prime prime
108	composite composite composite composite composite
109	prime prime prime prime prime
110	composite composite composite composite composite
111	composite composite composite composite composite
112	composite composite composite composite composite
113	prime prime prime prime prime
114	composite composite composite composite composite
115	composite composite composite composite composite
116	composite composite composite composite composite
117	composite composite composite composite composite
118	composite composite composite composite composite
119	composite composite composite composite composite
120	composite composite composite composite composite
121	composite composite composite composite composite
122	composite composite composite composite composite
123	composite composite composite composite composite
124	composite composite composite composite composite
125	composite composite composite composite composite
126	composite composite composite composite composite
127	prime prime prime prime prime
128	composite composite composite composite composite
129	composite composite composite composite composite
130	composite composite composite composite composite
131	prime prime prime prime prime
132	composite composite composite composite composite
133	composite composite composite composite composite
134	composite composite composite composite composite
135	composite composite composite composite composite
136	composite composite composite composite composite
137	prime prime prime prime prime
138	composite composite composite composite composite
139	prime prime prime prime prime
140	composite composite composite composite composite
141	composite composite composite composite composite
142	composite composite composite composite composite
143	composite composite composite composite composite
144	composite composite composite composite composite
145	composite composite composite composite composite
146	composite composite composite composite composite
147	composite composite composite composite composite
148	composite composite composite composite composite
149	prime prime prime prime prime
150	composite composite composite composite composite
151	prime prime prime prime prime
152	composite composite composite composite composite
153	composite composite composite composite composite
154	composite composite composite composite composite
155	composite composite composite composite composite
156	composite composite composite composite composite
157	prime prime prime prime prime
158	composite composite composite composite composite
159	composite composite composite composite composite
160	composite composite composite composite composite
161	composite composite composite composite composite
162	composite composite composite composite composite
163	prime prime prime prime prime
164	composite composite composite composite composite
165	composite composite composite composite composite
166	composite composite composite composite composite
167	prime prime prime prime prime
168	composite composite composite composite composite
169	composite composite composite composite composite
170	composite composite composite composite composite
171	composite composite composite composite composite
172	composite composite composite composite composite
173	prime prime prime prime prime
174	composite composite composite composite composite
175	composite composite composite composite composite
176	composite composite composite composite composite
177	composite composite composite composite composite
178	composite composite composite composite composite
179	prime prime prime prime prime
180	composite composite composite composite composite
181	prime prime prime prime prime
182	composite composite composite composite composite
183	composite composite composite composite composite
184	composite composite composite composite composite
185	composite composite composite composite composite
186	composite composite composite composite composite
187	composite composite composite composite composite
188	composite composite composite composite composite
189	composite composite composite composite composite
190	composite composite composite composite composite
191	prime prime prime prime prime
192	composite composite composite composite composite
193	prime prime prime prime prime
194	composite composite composite composite composite
195	composite composite composite composite composite
196	composite composite composite composite composite
197	prime prime prime prime prime
198	composite composite composite composite composite
199	prime prime prime prime prime
200	composite composite composite composite composite
201	composite composite composite composite composite
202	composite composite composite composite composite
203	composite composite composite composite composite
204	composite composite composite composite composite
205	composite composite composite composite composite
206	composite composite composite composite composite
207	composite composite composite composite composite
208	composite composite composite composite composite
209	composite composite composite composite composite
210	composite composite composite composite composite
211	prime prime prime prime prime
212	composite composite composite composite composite
213	composite composite composite composite composite
214	composite composite composite composite composite
215	composite composite composite composite composite
216	composite composite composite composite composite
217	composite composite composite composite composite
218	composite composite composite composite composite
219	composite composite composite composite composite
220	composite composite composite composite composite
221	composite composite composite composite composite
222	composite composite composite composite composite
223	prime prime prime prime prime
224	composite composite composite composite composite
225	composite composite composite composite composite
226	composite composite composite composite composite
227	prime prime prime prime prime
228	composite composite composite composite composite
229	prime prime prime prime prime
230	composite composite composite composite composite
231	composite composite composite composite composite
232	composite composite composite composite composite
233	prime prime prime prime prime
234	composite composite composite composite composite
235	composite composite composite composite composite
236	composite composite composite composite composite
237	composite composite composite composite composite
238	composite composite composite composite composite
239	prime prime prime prime prime
240	composite composite composite composite composite
241	prime prime prime prime prime
242	composite composite composite composite composite
243	composite composite composite composite composite
244	composite composite composite composite composite
245	composite composite composite composite composite
246	composite composite composite composite composite
247	composite composite composite composite composite
248	composite composite composite composite composite
249	composite composite composite composite composite
250	composite composite composite composite composite
251	prime prime prime prime prime
252	composite composite composite composite composite
253	composite composite composite composite composite
254	composite composite composite composite composite
255	composite composite composite composite composite
256	composite composite composite composite composite
257	prime prime prime prime prime
258	composite composite composite composite composite
259	composite composite composite composite composite
260	composite composite composite composite composite
261	composite composite composite composite composite
262	composite composite composite composite composite
263	prime prime prime prime prime
264	composite composite composite composite composite
265	composite composite composite composite composite
266	composite composite composite composite composite
267	composite composite composite composite composite
268	composite composite composite composite composite
269	prime prime prime prime prime
270	composite composite composite composite composite
271	prime prime prime prime prime
272	composite composite composite composite composite
273	composite composite composite composite composite
274	composite composite composite composite composite
275	composite composite composite composite composite
276	composite composite composite composite composite
277	prime prime prime prime prime
278	composite composite composite composite composite
279	composite composite composite composite composite
280	composite composite composite composite composite
281	prime prime prime prime prime
282	composite composite composite composite composite
283	prime prime prime prime prime
284	composite composite composite composite composite
285	composite composite composite composite composite
286	composite composite composite composite composite
287	composite composite composite composite composite
288	composite composite composite composite composite
289	composite composite composite composite composite
290	composite composite composite composite composite
291	composite composite composite composite composite
292	composite composite composite composite composite
293	prime prime prime prime prime
294	composite composite composite composite composite
295	composite composite composite composite composite
296	composite composite composite composite composite
297	composite composite composite composite composite
298	composite composite composite composite composite
299	composite composite composite composite composite
300	composite composite composite composite composite
301	composite composite composite composite composite
302	composite composite composite composite composite
303	composite composite composite composite composite
304	composite composite composite composite composite
305	composite composite composite composite composite
306	composite composite composite composite composite
307	prime prime prime prime prime
308	composite composite composite composite composite
309	composite composite composite composite composite
310	composite composite composite composite composite
311	prime prime prime prime prime
312	composite composite composite composite composite
313	prime prime prime prime prime
314	composite composite composite composite composite
315	composite composite composite composite composite
316	composite composite composite composite composite
317	prime prime prime prime prime
318	composite composite composite composite composite
319	composite composite composite composite composite
320	composite composite composite composite composite
321	composite composite composite composite composite
322	composite composite composite composite composite
323	composite composite composite composite composite
324	composite composite composite composite composite
325	composite composite composite composite composite
326	composite composite composite composite composite
327	composite composite composite composite composite
328	composite composite composite composite composite
329	composite composite composite composite composite
330	composite composite composite composite composite
331	prime prime prime prime prime
332	composite composite composite composite composite
333	composite composite composite composite composite
334	composite composite composite composite composite
335	composite composite composite composite composite
336	composite composite composite composite composite
337	prime prime prime prime prime
338	composite composite composite composite composite
339	composite composite composite composite composite
340	composite composite composite composite composite
341	composite composite composite composite composite
342	composite composite composite composite composite
343	composite composite composite composite composite
344	composite composite composite composite composite
345	composite composite composite composite composite
346	composite composite composite composite composite
347	prime prime prime prime prime
348	composite composite composite composite composite
349	prime prime prime prime prime
350	composite composite composite composite composite
351	composite composite composite composite composite
352	composite composite composite composite composite
353	prime prime prime prime prime
354	composite composite composite composite composite
355	composite composite composite composite composite
356	composite composite composite composite composite
357	composite composite composite composite composite
358	composite composite composite composite composite
359	prime prime prime prime prime
360	composite composite composite composite composite
361	composite composite composite composite composite
362	composite composite composite composite composite
363	composite composite composite composite composite
364	composite composite composite composite composite
365	composite composite composite composite composite
366	composite composite composite composite composite
367	prime prime prime prime prime
368	composite composite composite composite composite
369	composite composite composite composite composite
370	composite composite composite composite composite
371	composite composite composite composite composite
372	composite composite composite composite composite
373	prime prime prime prime prime
374	composite composite composite composite composite
375	composite composite composite composite composite
376	composite composite composite composite composite
377	composite composite composite composite composite
378	composite composite composite composite composite
379	prime prime prime prime prime
380	composite composite composite composite composite
381	composite composite composite composite composite
382	composite composite composite composite composite
383	prime prime prime prime prime
384	composite composite composite composite composite
385	composite composite composite composite composite
386	composite composite composite composite composite
387	composite composite composite composite composite
388	composite composite composite composite composite
389	prime prime prime prime prime
390	composite composite composite composite composite
391	composite composite composite composite composite
392	composite composite composite composite composite
393	composite composite composite composite composite
394	composite composite composite composite composite
395	composite composite composite composite composite
396	composite composite composite composite composite
397	prime prime prime prime prime
398	composite composite composite composite composite
399	composite composite composite composite composite
400	composite composite composite composite composite
401	prime prime prime prime prime
402	composite composite composite composite composite
403	composite composite composite composite composite
404	composite composite composite composite composite
405	composite composite composite composite composite
406	composite composite composite composite composite
407	composite composite composite composite composite
408	composite composite composite composite composite
409	prime prime prime prime prime
410	composite composite composite composite composite
411	composite composite composite composite composite
412	composite composite composite composite composite
413	composite composite composite composite composite
414	composite composite composite composite composite
415	composite composite composite composite composite
416	composite composite composite composite composite
417	composite composite composite composite composite
418	composite composite composite composite composite
419	prime prime prime prime prime
420	composite composite composite composite composite
421	prime prime prime prime prime
422	composite composite composite composite composite
423	composite composite composite composite composite
424	composite composite composite composite composite
425	composite composite composite composite composite
426	composite composite composite composite composite
427	composite composite composite composite composite
428	composite composite composite composite composite
429	composite composite composite composite composite
430	composite composite composite composite composite
431	prime prime prime prime prime
432	composite composite composite composite composite
433	prime prime prime prime prime
434	composite composite composite composite composite
435	composite composite composite composite composite
436	composite composite composite composite composite
437	composite composite composite composite composite
438	composite composite composite composite composite
439	prime prime prime prime prime
440	composite composite composite composite composite
441	composite composite composite composite composite
442	composite composite composite composite composite
443	prime prime prime prime prime
444	composite composite composite composite composite
445	composite composite composite composite composite
446	composite composite composite composite composite
447	composite composite composite composite composite
448	composite composite composite composite composite
449	prime prime prime prime prime
450	composite composite composite composite composite
451	composite composite composite composite composite
452	composite composite composite composite composite
453	composite composite composite composite composite
454	composite composite composite composite composite
455	composite composite composite composite composite
456	composite composite composite composite composite
457	prime prime prime prime prime
458	composite composite composite composite composite
459	composite composite composite composite composite
460	composite composite composite composite composite
461	prime prime prime prime prime
462	composite composite composite composite composite
463	prime prime prime prime prime
464	composite composite composite composite composite
465	composite composite composite composite composite
466	composite composite composite composite composite
467	prime prime prime prime prime
468	composite composite composite composite composite
469	composite composite composite composite composite
470	composite composite composite composite composite
471	composite composite composite composite composite
472	composite composite composite composite composite
473	composite composite composite composite composite
474	composite composite composite composite composite
475	composite composite composite composite composite
476	composite composite composite composite composite
477	composite composite composite composite composite
478	composite composite composite composite composite
479	prime prime prime prime prime
480	composite composite composite composite composite
481	composite composite composite composite composite
482	composite composite composite composite composite
483	composite composite composite composite composite
484	composite composite composite composite composite
485	composite composite composite composite composite
486	composite composite composite composite composite
487	prime prime prime prime prime
488	composite composite composite composite composite
489	composite composite composite composite composite
490	composite composite composite composite composite
491	prime prime prime prime prime
492	composite composite composite composite composite
493	composite composite composite composite composite
494	composite composite composite composite composite
495	composite composite composite composite composite
496	composite composite composite composite composite
497	composite composite composite composite composite
498	composite composite composite composite composite
499	prime prime prime prime prime
500	composite composite composite composite composite
501	composite composite composite composite composite
502	composite composite composite composite composite
503	prime prime prime prime prime
504	composite composite composite composite composite
505	composite composite composite composite composite
506	composite composite composite composite composite
507	composite composite composite composite composite
508	composite composite composite composite composite
509	prime prime prime prime prime
510	composite composite composite composite composite
511	composite composite composite composite composite
512	composite composite composite composite composite
513	composite composite composite composite composite
514	composite composite composite composite composite
515	composite composite composite composite composite
516	composite composite composite composite composite
517	composite composite composite composite composite
518	composite composite composite composite composite
519	composite composite composite composite composite
520	composite composite composite composite composite
521	prime prime prime prime prime
522	composite composite composite composite composite
523	prime prime prime prime prime
524	composite composite composite composite composite
525	composite composite composite composite composite
526	composite composite composite composite composite
527	composite composite composite composite composite
528	composite composite composite composite composite
529	composite composite composite composite composite
530	composite composite composite composite composite
531	composite composite composite composite composite
532	composite composite composite composite composite
533	composite composite composite composite composite
534	composite composite composite composite composite
535	composite composite composite composite composite
536	composite composite composite composite composite
537	composite composite composite composite composite
538	composite composite composite composite composite
539	composite composite composite composite composite
540	composite composite composite composite composite
541	prime prime prime prime prime
542	composite composite composite composite composite
543	composite composite composite composite composite
544	composite composite composite composite composite
545	composite composite composite composite composite
546	composite composite composite composite composite
547	prime prime prime prime prime
548	composite composite composite composite composite
549	composite composite composite composite composite
550	composite composite composite composite composite
551	composite composite composite composite composite
552	composite composite composite composite composite
553	composite composite composite composite composite
554	composite composite composite composite composite
555	composite composite composite composite composite
556	composite composite composite composite composite
557	prime prime prime prime prime
558	composite composite composite composite composite
559	composite composite composite composite composite
560	composite composite composite composite composite
561	composite composite composite composite composite
562	composite composite composite composite composite
563	prime prime prime prime prime
564	composite composite composite composite composite
565	composite composite composite composite composite
566	composite composite composite composite composite
567	composite composite composite composite composite
568	composite composite composite composite composite
569	prime prime prime prime prime
570	composite composite composite composite composite
571	prime prime prime prime prime
572	composite composite composite composite composite
573	composite composite composite composite composite
574	composite composite composite composite composite
575	composite composite composite composite composite
576	composite composite composite composite composite
577	prime prime prime prime prime
578	composite composite composite composite composite
579	composite composite composite composite composite
580	composite composite composite composite composite
581	composite composite composite composite composite
582	composite composite composite composite composite
583	composite composite composite composite composite
584	composite composite composite composite composite
585	composite composite composite composite composite
586	composite composite composite composite composite
587	prime prime prime prime prime
588	composite composite composite composite composite
589	composite composite composite composite composite
590	composite composite composite composite composite
591	composite composite composite composite composite
592	composite composite composite composite composite
593	prime prime prime prime prime
594	composite composite composite composite composite
595	composite composite composite composite composite
596	composite composite composite composite composite
597	composite composite composite composite composite
598	composite composite composite composite composite
599	prime prime prime prime prime
600	composite composite composite composite composite
601	prime prime prime prime prime
602	composite composite composite composite composite
603	composite composite composite composite composite
604	composite composite composite composite composite
605	composite composite composite composite composite
606	composite composite composite composite composite
607	prime prime prime prime prime
608	composite composite composite composite composite
609	composite composite composite composite composite
610	composite composite composite composite composite
611	composite composite composite composite composite
612	composite composite composite composite composite
613	prime prime prime prime prime
614	composite composite composite composite composite
615	composite composite composite composite composite
616	composite composite composite composite composite
617	prime prime prime prime prime
618	composite composite composite composite composite
619	prime prime prime prime prime
620	composite composite composite composite composite
621	composite composite composite composite composite
622	composite composite composite composite composite
623	composite composite composite composite composite
624	composite composite composite composite composite
625	composite composite composite composite composite
626	composite composite composite composite composite
627	composite composite composite composite composite
628	composite composite composite composite composite
629	composite composite composite composite composite
630	composite composite composite composite composite
631	prime prime prime prime prime
632	composite composite composite composite composite
633	composite composite composite composite composite
634	composite composite composite composite composite
635	composite composite composite composite composite
636	composite composite composite composite composite
637	composite composite composite composite composite
638	composite composite composite composite composite
639	composite composite composite composite composite
640	composite composite composite composite composite
641	prime prime prime prime prime
642	composite composite composite composite composite
643	prime prime prime prime prime
644	composite composite composite composite composite
645	composite composite composite composite composite
646	composite composite composite composite composite
647	prime prime prime prime prime
648	composite composite composite composite composite
649	composite composite composite composite composite
650	composite composite composite composite composite
651	composite composite composite composite composite
652	composite composite composite composite composite
653	prime prime prime prime prime
654	composite composite composite composite composite
655	composite composite composite composite composite
656	composite composite composite composite composite
657	composite composite composite composite composite
658	composite composite composite composite composite
659	prime prime prime prime prime
660	composite composite composite composite composite
661	prime prime prime prime prime
662	composite composite composite composite composite
663	composite composite composite composite composite
664	composite composite composite composite composite
665	composite composite composite composite composite
666	composite composite composite composite composite
667	composite composite composite composite composite
668	composite composite composite composite composite
669	composite composite composite composite composite
670	composite composite composite composite composite
671	composite composite composite composite composite
672	composite composite composite composite composite
673	prime prime prime prime prime
674	composite composite composite composite composite
675	composite composite composite composite composite
676	composite composite composite composite composite
677	prime prime prime prime prime
678	composite composite composite composite composite
679	composite composite composite composite composite
680	composite composite composite composite composite
681	composite composite composite composite composite
682	composite composite composite composite composite
683	prime prime prime prime prime
684	composite composite composite composite composite
685	composite composite composite composite composite
686	composite composite composite composite composite
687	composite composite composite composite composite
688	composite composite composite composite composite
689	composite composite composite composite composite
690	composite composite composite composite composite
691	prime prime prime prime prime
692	composite composite composite composite composite
693	composite composite composite composite composite
694	composite composite composite composite composite
695	composite composite composite composite composite
696	composite composite composite composite composite
697	composite composite composite composite composite
698	composite composite composite composite composite
699	composite composite composite composite composite
700	composite composite composite composite composite
701	prime prime prime prime prime
702	composite composite composite composite composite
703	composite composite composite composite composite
704	composite composite composite composite composite
705	composite composite composite composite composite
706	composite composite composite composite composite
707	composite composite composite composite composite
708	composite composite composite composite composite
709	prime prime prime prime prime
710	composite composite composite composite composite
711	composite composite composite composite composite
712	composite composite composite composite composite
713	composite composite composite composite composite
714	composite composite composite composite composite
715	composite composite composite composite composite
716	composite composite composite composite composite
717	composite composite composite composite composite
718	composite composite composite composite composite
719	prime prime prime prime prime
720	composite composite composite composite composite
721	composite composite composite composite composite
722	composite composite composite composite composite
723	composite composite composite composite composite
724	composite composite composite composite composite
725	composite composite composite composite composite
726	composite composite composite composite composite
727	prime prime prime prime prime
728	composite composite composite composite composite
729	composite composite composite composite composite
730	composite composite composite composite composite
731	composite composite composite composite composite
732	composite composite composite composite composite
733	prime prime prime prime prime
734	composite composite composite composite composite
735	composite composite composite composite composite
736	composite composite composite composite composite
737	composite composite composite composite composite
738	composite composite composite composite composite
739	prime prime prime prime prime
740	composite composite composite composite composite
741	composite composite composite composite composite
742	composite composite composite composite composite
743	prime prime prime prime prime
744	composite composite composite composite composite
745	composite composite composite composite composite
746	composite composite composite composite composite
747	composite composite composite composite composite
748	composite composite composite composite composite
749	composite composite composite composite composite
750	composite composite composite composite composite
751	prime prime prime prime prime
752	composite composite composite composite composite
753	composite composite composite composite composite
754	composite composite composite composite composite
755	composite composite composite composite composite
756	composite composite composite composite composite
757	prime prime prime prime prime
758	composite composite composite composite composite
759	composite composite composite composite composite
760	composite composite composite composite composite
761	prime prime prime prime prime
762	composite composite composite composite composite
763	composite composite composite composite composite
764	composite composite composite composite composite
765	composite composite composite composite composite
766	composite composite composite composite composite
767	composite composite composite composite composite
768	composite composite composite composite composite
769	prime prime prime prime prime
770	composite composite composite composite composite
771	composite composite composite composite composite
772	composite composite composite composite composite
773	prime prime prime prime prime
774	composite composite composite composite composite
775	composite composite composite composite composite
776	composite composite composite composite composite
777	composite composite composite composite composite
778	composite composite composite composite composite
779	composite composite composite composite composite
780	composite composite composite composite composite
781	composite composite composite composite composite
782	composite composite composite composite composite
783	composite composite composite composite composite
784	composite composite composite composite composite
785	composite composite composite composite composite
786	composite composite composite composite composite
787	prime prime prime prime prime
788	composite composite composite composite composite
789	composite composite composite composite composite
790	composite composite composite composite composite
791	composite composite composite composite composite
792	composite composite composite composite composite
793	composite composite composite composite composite
794	composite composite composite composite composite
795	composite composite composite composite composite
796	composite composite composite composite composite
797	prime prime prime prime prime
798	composite composite composite composite composite
799	composite composite composite composite composite
800	composite composite composite composite composite
801	composite composite composite composite composite
802	composite composite composite composite composite
803	composite composite composite composite composite
804	composite composite composite composite composite
805	composite composite composite composite composite
806	composite composite composite composite composite
807	composite composite composite composite composite
808	composite composite composite composite composite
809	prime prime prime prime prime
810	composite composite composite composite composite
811	prime prime prime prime prime
812	composite composite composite composite composite
813	composite composite composite composite composite
814	composite composite composite composite composite
815	composite composite composite composite composite
816	composite composite composite composite composite
817	composite composite composite composite composite
818	composite composite composite composite composite
819	composite composite composite composite composite
820	composite composite composite composite composite
821	prime prime prime prime prime
822	composite composite composite composite composite
823	prime prime prime prime prime
824	composite composite composite composite composite
825	composite composite composite composite composite
826	composite composite composite composite composite
827	prime prime prime prime prime
828	composite composite composite composite composite
829	prime prime prime prime prime
830	composite composite composite composite composite
831	composite composite composite composite composite
832	composite composite composite composite composite
833	composite composite composite composite composite
834	composite composite composite composite composite
835	composite composite composite composite composite
836	composite composite composite composite composite
837	composite composite composite composite composite
838	composite composite composite composite composite
839	prime prime prime prime prime
840	composite composite composite composite composite
841	composite composite composite composite composite
842	composite composite composite composite composite
843	composite composite composite composite composite
844	composite composite composite composite composite
845	composite composite composite composite composite
846	composite composite composite composite composite
847	composite composite composite composite composite
848	composite composite composite composite composite
849	composite composite composite composite composite
850	composite composite composite composite composite
851	composite composite composite composite composite
852	composite composite composite composite composite
853	prime prime prime prime prime
854	composite composite composite composite composite
855	composite composite composite composite composite
856	composite composite composite composite composite
857	prime prime prime prime prime
858	composite composite composite composite composite
859	prime prime prime prime prime
860	composite composite composite composite composite
861	composite composite composite composite composite
862	composite composite composite composite composite
863	prime prime prime prime prime
864	composite composite composite composite composite
865	composite composite composite composite composite
866	composite composite composite composite composite
867	composite composite composite composite composite
868	composite composite composite composite composite
869	composite composite composite composite composite
870	composite composite composite composite composite
871	composite composite composite composite composite
872	composite composite composite composite composite
873	composite composite composite composite composite
874	composite composite composite composite composite
875	composite composite composite composite composite
876	composite composite composite composite composite
877	prime prime prime prime prime
878	composite composite composite composite composite
879	composite composite composite composite composite
880	composite composite composite composite composite
881	prime prime prime prime prime
882	composite composite composite composite composite
883	prime prime prime prime prime
884	composite composite composite composite composite
885	composite composite composite composite composite
886	composite composite composite composite composite
887	prime prime prime prime prime
888	composite composite composite composite composite
889	composite composite composite composite composite
890	composite composite composite composite composite
891	composite composite composite composite composite
892	composite composite composite composite composite
893	composite composite composite composite composite
894	composite composite composite composite composite
895	composite composite composite composite composite
896	composite composite composite composite composite
897	composite composite composite composite composite
898	composite composite composite composite composite
899	composite composite composite composite composite
900	composite composite composite composite composite
901	composite composite composite composite composite
902	composite composite composite composite composite
903	composite composite composite composite composite
904	composite composite composite composite composite
905	composite composite composite composite composite
906	composite composite composite composite composite
907	prime prime prime prime prime
908	composite composite composite composite composite
909	composite composite composite composite composite
910	composite composite composite composite composite
911	prime prime prime prime prime
912	composite composite composite composite composite
913	composite composite composite composite composite
914	composite composite composite composite composite
915	composite composite composite composite composite
916	composite composite composite composite composite
917	composite composite composite composite composite
918	composite composite composite composite composite
919	prime prime prime prime prime
920	composite composite composite composite composite
921	composite composite composite composite composite
922	composite composite composite composite composite
923	composite composite composite composite composite
924	composite composite composite composite composite
925	composite composite composite composite composite
926	composite composite composite composite composite
927	composite composite composite composite composite
928	composite composite composite composite composite
929	prime prime prime prime prime
930	composite composite composite composite composite
931	composite composite composite composite composite
932	composite composite composite composite composite
933	composite composite composite composite composite
934	composite composite composite composite composite
935	composite composite composite composite composite
936	composite composite composite composite composite
937	prime prime prime prime prime
938	composite composite composite composite composite
939	composite composite composite composite composite
940	composite composite composite composite composite
941	prime prime prime prime prime
942	composite composite composite composite composite
943	composite composite composite composite composite
944	composite composite composite composite composite
945	composite composite composite composite composite
946	composite composite composite composite composite
947	prime prime prime prime prime
948	composite composite composite composite composite
949	composite composite composite composite composite
950	composite composite composite composite composite
951	composite composite composite composite composite
952	composite composite composite composite composite
953	prime prime prime prime prime
954	composite composite composite composite composite
955	composite composite composite composite composite
956	composite composite composite composite composite
957	composite composite composite composite composite
958	composite composite composite composite composite
959	composite composite composite composite composite
960	composite composite composite composite composite
961	composite composite composite composite composite
962	composite composite composite composite composite
963	composite composite composite composite composite
964	composite composite composite composite composite
965	composite composite composite composite composite
966	composite composite composite composite composite
967	prime prime prime prime prime
968	composite composite composite composite composite
969	composite composite composite composite composite
970	composite composite composite composite composite
971	prime prime prime prime prime
972	composite composite composite composite composite
973	composite composite composite composite composite
974	composite composite composite composite composite
975	composite composite composite composite composite
976	composite composite composite composite composite
977	prime prime prime prime prime
978	composite composite composite composite composite
979	composite composite composite composite composite
980	composite composite composite composite composite
981	composite composite composite composite composite
982	composite composite composite composite composite
983	prime prime prime prime prime
984	composite composite composite composite composite
985	composite composite composite composite composite
986	composite composite composite composite composite
987	composite composite composite composite composite
988	composite composite composite composite composite
989	composite composite composite composite composite
990	composite composite composite composite composite
991	prime prime prime prime prime
992	composite composite composite composite composite
993	composite composite composite composite composite
994	composite composite composite composite composite
995	composite composite composite composite composite
996	composite composite composite composite composite
997	prime prime prime prime prime
998	composite composite composite composite composite
999	composite composite composite composite composite
>>> 

Intuitively, it can be seen that these five methods can get the same answer. In the actual program, we generally do not print the answer but check it inside the program with logic.

In general, check the program is correct for millions of times does not take more than 1 minute. And with such a large amount of data, it is almost certain that the program is correct. (Sometimes we need special value detection, that is, enter some special values to check the correctness of the program, such as 0 or 1 or 2, because some programs work well under random numbers, but special values will not work.)

Statistics

Start time of this page: February 2, 2022

Completion time of this page: February 4, 2022