ProjectEuler 362 Squarefree factors - 拼圖

By Audriana
at 2011-12-19T19:31

Table of Contents

※ [本文轉錄自 chyrliin 信箱]

作者: babufong (嗶嗶) 看板: puzzle
標題: [中譯] ProjectEuler 362 Squarefree factors
時間: Sun Dec 11 15:30:32 2011

362. Squarefree factors

http://projecteuler.net/problem=362

來看看 54 這個數字

54 可以拆成 7 種全然不同的一個或多個因數相乘的組成方法，而這些因數都大於 1

如：54 , 2 X 27 , 3 X 18 , 6 X 9 , 3 X 3 X 6 , 2 X 3 X 9 和 2 X 3 X 3 X 3

如果我們要求這些因數都要是「無平方數因數」的數所組成，那就只剩下 2 種組法：

3 X 3 X 6 和 2 X 3 X 3 X 3

Fsf(n) 為 n 有幾種上述條件的方法去組成，所以 Fsf(54) = 2

S(n) 為 ΣFsf(k) , k = 2 到 n

已知 S(100) = 193

請求出 S(10000000000)

--

All Comments

By Linda
at 2011-12-23T15:55

好酷

By Sandy
at 2011-12-26T01:55

OEIS有數列 (http://oeis.org/A050320 ) 問題在於 10^10...

By Carolina Franco
at 2011-12-26T23:18

如果要跑暴力破解法應該不會那麼難
不過要跑一分鐘以內就有點難度

By Gilbert
at 2011-12-27T03:29

OEIS中已經有說同樣的prime signature 其a(n)是一樣的

By Candice
at 2011-12-29T23:34

所以不必每一個數都去算其a(n), 同樣的prime signature

By Gary
at 2012-01-02T09:01

算一就好, 並存到表格內(應該是Hash)，遇到同樣的prime
signature, 再從hash table取出即可

By Sandy
at 2012-01-04T08:22

素數的枚舉，也不用枚舉到10^10即可, 枚舉到10^8即可

By Mary
at 2012-01-09T00:41

大如10^8的素數,假若為p, p*1~p*100其a(n)等於101~101*100

By Olive
at 2012-01-11T11:50

所以只要算出小於(10^10)/1,(10^10)/2,...,(10^10)/100
的素數個數即可

By Jake
at 2012-01-13T02:45

我的方法, 如果是用C++加上現在主流的PC(core i7)

By Tristan Cohan
at 2012-01-17T09:46

應該是十分鐘以內可以跑出結果

By Margaret
at 2012-01-18T04:25

感謝企鵝靈解救文章！

By Enid
at 2012-01-19T05:44

結果真的是帕索不小心刪掉的...XD

By Mary
at 2012-01-20T08:48

= = 不過為什麼企鵝靈找得到文章呢？我都找不到.....

Related Posts

歲末小板聚之秘密盒不見了

By Skylar Davis
at 2011-12-17T22:24

這次板聚有兩個帥哥、兩個型男、兩個替代役、兩個愛買益智玩具、兩個愛吃速食等人到場。本來我可以很準時到的，但秘密盒不在我以為的那個地方，結果整整花掉我兩個小時的時間，更慘的是還沒找到。雖然反復的安慰自己反正也很少在玩，就算遺失也沒關係，但還是有一點不甘心。老闆和老葉都以為那個「找不到」是 ...

一個有趣的解謎網站 www.rankk.org

By Todd Johnson
at 2011-12-16T23:40

※ [本文轉錄自 Python 看板 #1EwBjtqy ] 作者: autumned (autumned) 看板: Python 標題: [閒聊] 一個有趣的解謎網站時間: Wed Dec 14 23:06:28 2011 www.rankk.org 如題雖然不像python challenge全 ...

禮拜六圓山育樂益玩之旅

By Christine
at 2011-12-15T00:02

百年即將進入尾聲，歲末板遊慶聖誕。圓山育樂中心益玩之旅— 時間12月17日早上11點到下午三點，集合地點圓山站一號出口，門票全票30元半票15元。當天帕索和企鵝均會到場伴遊，有志一同者請站內信報名參加，歡迎共襄盛舉。更多圓山益玩資訊請查閱 #1Egzt ...

梯形切割拼成平行四邊形

By Xanthe
at 2011-12-14T23:05

這題目出現在我女兒小五的數學習作將一個等腰梯形切割成數塊，拼成平行四邊形除了攔腰切開中線之外，還有別的方法嗎？ __________ _________________ \________/ ----andgt; \________/_______\ \______/ -- ...

喜歡拼圖夥伴們, 可以進來看看喔

By Jacob
at 2011-12-14T15:22

※ [本文轉錄自 Kaohsiung 看板 #1Ew4t8Yu ] 作者: jodoken (kk) 看板: Kaohsiung 標題: [活動] 喜歡拼圖夥伴們, 可以進來看看喔時間: Wed Dec 14 15:18:30 2011 我們最近新開了一間拼圖店(凱利‧拼‧世界) 只要五分鐘拼完立 ...