2013年7月11日 星期四

1180 - Perfect Numbers

在古希臘時期,對於數學領域就有極大的貢獻,特別是在這個時代的 歐幾里德(Euclid) 與 畢達哥拉斯(Pythagoras),至今有 23 本幾何原本(Euclid's Elements) 仍是數學研究的基礎。

歐幾里德對於畢達哥拉斯所提出的問題有重要的貢獻,其一是找到完美數(perfect number),例如 6 就是個完美數,其所有小於它自己的因數總合等於自己(1 + 2 + 3 = 6),另一個例子是 28,因為 28 = 1 + 2 + 4 + 7 + 14,且 1, 2, ,4 , 7, 14 都是 28 個因數。

在幾何原本第九卷中,歐幾理德找到所有偶數的完美數(這個證明過了很久才被證實,最後在 20 世紀才得到所有完美數都是偶數)。歐幾里德得到一個偶數的完美數會符合下列的格式:
2p-1(2p - 1)
其中 p  和 2p - 1 都是質數。

在兩千年後,歐拉(Leonhard Euler) 證明了歐幾里德的理論,所有偶數的完美數一定會符合歐幾里德格式,例如 6 和 8:
6 = 22-1(22 -1),  28 = 23-1(23 - 1)
完美數非常稀少,在 1975 年,也只有 24 個完美數被找到,其中前四個是 6, 28, 496, 8128。相對應的 p 為 2, 3, 5, 7。

給定一個 p (不一定是質數),必須決定 2p-1(2p - 1) 是否為完美數,假設題目中的最大完美數不超過 233



Input 

輸入包含兩行,第一行表示接下來有多少個整數行第二行,而第二行有數個 p 的詢問。

Output 

對於每個 p 輸出 "Yes" 或 "No"。
如果可以產生完美數輸出 "Yes",反之輸出 "No"。

Sample Input 

  
6 
2,3,4,5,6,7

Sample Output 

  
Yes 
Yes 
No 
Yes 
No 
Yes