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。