GRE/质数指南

质数

质数只能被自身和 1 整除。

1 到 100 之间的质数如下所示

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

一些数字，例如 51、57 或 93，看起来像质数，但实际上可以被一个奇特的质数整除。这三个分别可以被 17、19 和 31 整除。

非质数可以分解成其质因数。

“因数”是指一个较大的数字可以被其整除的数字。非质数可以使用因数树分解成其质因数。

24

         |     |
       2       12
              |     |
            2        6
                    |   |
                   2     3

 24 = 2(2)(2)(3) or 23(3)

这个表达式被称为 24 的“质因数分解”。在分解数字时，通常最容易先尽可能地除以 2 和 3。

练习

1. 100 的质因数分解是什么？

2. 大于 50 小于 60 的质数有多少个？

3. 将 372 表示为质数的乘积。

练习题答案

1. 2²(5²) 或 (2)(2)(5)(5)

质因数分解可以通过画因数树来实现 - 选择一个数字可以分解成任意两个数字，然后向下分解。

100

          /      \
        4        25
      /    \     /    \
    2      2  5     5

分支的底部是质因数。首先选择哪两个数字并不重要。所有因数树都将得出相同的数字。

100

          /      \
        5        20
      	      /    \

2 10 / \

	          2      5

2. 两个 - 53 和 59。

51 可以被 17 整除，而 57 可以被 19 整除。

3. 2²(3)(31) 或 2(2)(3)(31)

            372
         /       \
       2        186
                /     \
              2       93
                      /    \
                    3     31

正如你所看到的，在分解时，通常更容易首先提取 2 或 3。