# 9973是质数还是合数？PrimeSmash!——适合无聊时玩的消质数游戏

PrimeSmash!

• iOS
• MacOS
• Android（可能）

【用户投递】

## 一句简介

Touch, Smash, and Remember prime numbers the fun way!

（不知道怎么介绍，就把官方介绍的第一句话贴上去了）

（至少比单纯的切水果更有意义一点

## 官方网站 && 应用商店地址

Android……没找到

https://www.taptap.com/app/158963

Perhaps the easiest way to see whether a number that is not very big is prime or not is by trial.

Suppose that n is a positive integer. n is not prime if and only if there are two integers s, t greater than one such that n = st. Without loss of generality, suppose that s \leq t. Hence s^2 \leq n, which is just s \leq \sqrt{n}. We have the following useful proposition:

Suppose that n is a positive integer. n is not prime if and only if there exists an integer not greater than \sqrt{n} which divides n.

Suppose that p is a prime number greater than three. It is not hard to verify that six cannot divide p or p - 2 or p - 3 or p - 4. Hence all prime numbers greater than three must be of the form 6k + 1 or 6k - 1, in which k is an integer.

Now let’s see whether N = 9\,973 is prime or not.

Clearly neither two or three divides N. \sqrt{N} is greater than 99 and less than 100. Hence it suffices to check whether there is a prime number which is less than 100 and divides N. There are exactly twenty-five prime numbers which is greater than one and less than a hundred:

2   3   5   7   11
13  17  19  23  29
31  37  41  43  47
53  59  61  67  71
73  79  83  89  97


None of the numbers above divides N:

2 | 9 973 - 1
3 | 9 973 - 1
5 | 9 973 - 3
7 | 98; 7 | 9 898; 9 973 - 9 898 = 75; 7 does not divide 75
11 | 9 900; 9 973 - 9 900 = 73; 11 does not divide 73
13 | 9 100; 9 973 - 9 100 = 873;
13 | 780; 873 - 780 = 93; 13 does not divide 93
17 | 10 200; 10 200 - 9 973 = 227;
17 | 170; 227 - 170 = 57; 17 does not divide 57
19 | 9 500; 9 973 - 9 500 = 473;
19 | 380; 473 - 380 = 97; 19 does not divide 97
23 | 9 200; 9 973 - 9 200 = 793;
23 | 690; 793 - 690 = 103; 23 does not divide 103
29 | 8 700; 9 973 - 8 700 = 1 273;
29 | 1 160; 1 273 - 1 160 = 113; 29 does not divide 113
31 | 9 300; 9 973 - 9 300 = 673;
31 | 620; 673 - 620 = 53; 31 does not divide 53
37 | 111; 111 | 9 990; 9 990 - 9 973 = 17; 37 does not divide 17
41 | 8 200; 9 973 - 8 200 = 1 773;
41 | 41^2 = 1 681; 1 773 - 1 681 = 92; 41 does not divide 92
43 | 8 600; 9 973 - 8 600 = 1 373;
43 | 860; 1 373 - 860 = 513;
43 | 430; 513 - 430 = 83; 43 does not divide 83
47 | 9 400; 9 973 - 9 400 = 573;
47 | 470; 573 - 470 = 103; 47 does not divide 103
53 | 10 600; 10 600 - 9 973 = 627;
53 | 530; 627 - 530 = 97; 53 does not divide 97
59 | 11 800; 11 800 - 9 973 = 1 827;
59 | 1 180; 1 827 - 1 180 = 647;
59 | 590; 647 - 590 = 57; 59 does not divide 57
61 | 12 200; 12 200 - 9 973 = 2 227;
61 | 2 440; 2 440 - 2 227 = 213; 61 does not divide 213
67 | 13 400; 12 200 - 9 973 = 3 427;
67 | 2 010; 3 427 - 2 010 = 1 417;
67 | 1 340; 1 417 - 1 340 = 77; 67 does not divide 77
71 | 7 100; 9 973 - 7 100 = 2 873;
71 | 2 130; 2 873 - 2 130 = 743;
71 | 710; 743 - 710 = 33; 71 does not divide 33
73 | 7 300; 9 973 - 7 300 = 2 673;
73 | 2 190; 2 673 - 2 190 = 483;
73 | 438; 483 - 438 = 45; 73 does not divide 45
79 | 7 900; 9 973 - 7 900 = 2 073;
79 | 2 370; 2 370 - 2 073 = 297; 79 does not divide 297
83 | 8 300; 9 973 - 8 300 = 1 673;
83 | 1 660; 1 673 - 1 660 = 13; 83 does not divide 13
89 | 8 900; 9 973 - 8 900 = 1 073;
89 | 890; 1 073 - 890 = 183; 89 does not divide 183
97 | 9 700; 9 973 - 9 700 = 273;
97 | 194; 273 - 194 = 79; 97 does not divide 79


Hence N must be prime.