切換
舊版
前往
大廳
主題

ZeroJudge - c666: 質數乘積 解題心得

Not In My Back Yard | 2018-07-28 23:10:33 | 巴幣 0 | 人氣 671

題目連結:c666: 質數乘積

題目大意:給定 N(N < 5001),輸出前N個質數的乘積。

思維:
  雖然看似簡單,但是對於沒有內建大數運算的語言不大方便(例如C、C++等等比較中低階的語言。雖然Java有內建,但是本人比較習慣C++),因為N=5000時,答案有20975位數。

  要實作大數很簡單,使用本來一般整數舊有的乘法 + 陣列即可,且因為本題的乘數(或是被乘數,看要哪一方)是可以容納進Int型態的質數,所以更簡潔。

  假設現有一數210,要乘以11。可以先將210拆成2、10分別儲存在陣列的不同位置,並假設一格陣列位置只能存0~99,多餘的要進位到下一格陣列位置;然後,11去跟10乘,得110,並發現大於了我們假定的陣列上限;於是便將110除以100,得到餘數10,把商數1進到下一格位置;之後11再乘以原先的2(剛剛的1是進位來的,請別算進去),得22。再加1,得23。
  於是,我們得到了23、10這樣子的陣列,即是我們要的答案。

註:若有123、7這樣子的陣列內容(進位上界是1000的話),代表是123007,而非1237喔。



此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大們可以提出來討論。

創作回應

更多創作