創作內容

0 GP

ZeroJudge - d423: 10856 - Recover Factorial 解題心得

作者:Not In My Back Yard│2018-12-17 22:44:13│巴幣:0│人氣:325
題目連結:


題目大意:
階乘可以寫作一連串的質數相乘,例如 4!=2 × 2 × 2 × 3 ,有「4個」質因數。

現給定一正整數 N ( 0 ≦ N ≦ 10, 000, 001 ),請找出 X! 之質因數個數為 N 個的最小可能之 X 為何?若不存在這樣子的 X ,請輸出「Not possible.」



範例輸入:
4
240
241
-1



範例輸出:
Case 1: 4!
Case 2: 101!
Case 3: Not possible.



解題思維:
仔細觀察質因數個數的成長: 1!,0 個; 2!,1 個; 3!,2 個; 4!,4 個……很明顯就只是一直加下一個數字的質因數個數。因此我們可以利用這樣子的特性去建表。

當然,在為每個整數求質因數的個數之前也要先建一個質數表。可以用埃式篩法加快建質數表的速度,這方法可以在我之前的一些關於質數的程式碼裡也可見到。

然後,再用大家應該耳熟能詳的 O(sqrt(N)) 的方法(原理跟檢查是否為質數,幾乎一樣)為每個數字找出質因數個數。

然後開一個陣列大小為 10, 000, 001 ,每個索引值本身代表質因數的個數。因此第0個位置為0,第一個位置為2,第二個位置因為找不到所以設為 -1……以此類推。

最後,在輸入的時候,輸入進什麼數字就到上述的陣列去尋找。對應位置不是 -1 的就輸出儲存的值;反之,輸出「Not Possible」。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4229931
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|質數

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeorJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

leo25127大家
穿越奇幻日常系小說『公爵家的獨生子』在小屋內更新最新一章囉,來看看ㄎ一ㄤ少爺怎麼在異世界作威作福吧!看更多我要大聲說昨天18:07


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】