2013年11月11日 星期一

[UVA]Simply Emirp

CPE 10428、UVA 10235程式解題。


















































解題觀念:



此題最主要就是判斷是否為質數。

若某數為質數且將數字反轉後也是質數,且和原數不同,則稱該數為emirp

(EX : 17為質數,反轉後71也是質數,且17不等於71,則17為emirp。)

但如果原數為質數,但反轉後和原數相同,則該數為prime

(EX : 131為質數,反轉後依然為131,不是emirp。為prime。)

不是質數就直接輸出 is not prime。

所以這題需要做資料反轉的處理。

還有很重要的一點,一定要先做好質數表,才能避免逾時


解題步驟:

先用StringBuffer類別宣告一個ans物件,等等要用來反轉字串。

宣告兩個整數a1,a2;在宣告兩個字串s1,s2。等一下用來存放資料。

再來就是建構質數表。
(*這題如果沒有事先建構質數表的話,不管你怎麼寫都一定會逾時。)
 
至於質數表的建構方式在這邊不多說,可以到此網站去參考=>演算法筆記-質數表建立

之後的就是做資料處理。

輸入整數後先轉字串(Integer.toString()),再轉為StringBuffer的物件(ans.newStringBuffer(a1)),

將它反轉(ans.reverse()),反轉後的資料再轉回字串(ans.toString())存在s2,

最後轉回整數(Integer.toString())存到a2。
(我在程式碼上面有做註解,如果純文字看不懂可以直接看程式碼。)

之後做if判斷,檢查此數字是否有在質數表內(prime[a1]是否等於true),如果不是就直接輸出not prime。

如果符合再判斷數字反轉後是否為質數(prime[a1]是否等於prime[a2]),且結果是否不同(a1是否不等於a2)。如果符合則印出emirp,不符合則印出prime。


EX:

179

179先轉字串存到s1,再轉為StringBuffer物件=>ans,之後反轉=>ans=971,

再轉回字串 s2=971,最後轉回整數 a2=971。

判斷a1=179是否為質數,符合。

在判斷971是否和179一樣為質數,且179是否不等於971,符合。

印出179 is prime.


By  小K

沒有留言:

張貼留言