10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge

Slides:



Advertisements
Similar presentations
不定積分 不定積分的概念 不定積分的定義 16 不定積分的概念 16.1 不定積分的概念 以下是一些常用的積分公式。
Advertisements

數數 8. 認識 100 以內的數 讓孩子仔細觀察表格,並說 出以下規律: 每行有 ___ 個數,前一個比 後一個少 ___ ; 每列有 ___ 個數;下一個比 上一個多 ___ ; 右斜看發現下一個數比上一 個數多 ___; 左斜看發現上一個數比下一 個數少 ___ ; 數一數,一位數有 ___.
數學本質概念 因數與倍數 指導教授:林宜臻老師 學生:廖冠惠 歐妍汝
11010: Tic-Tac-Tough ★★★★☆ 題組: Problem Set Archive with Online Judge
Dropping water balloons
質數(prime).
因數與倍數 數學教材教法 TKU96B 鄭怡婷.
認識倍數(一) 設計者:建功國小 盧建宏.
TQC+ JAVA全國教師研習會 PLWeb 程式設計練習平台 簡介.
密碼學與網路安全 第8章 數論介紹.
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
順德聯誼總會梁潔華小學 六年級 數學科 下學期 數形.
資料結構 第1章 導論.
1.3 在整除性問題之應用 附加例題 3 © 文達出版 (香港 )有限公司.
10298: Power Strings ★★☆☆☆ 題組:Problem Set Archive with Online Judge
第一章 直角坐標系 1-1 數系的發展.
五 年 級 上 學 期 數 學 科 100 以 內 的 質 數 作者:陳長培 老師 深 信 學 校.
10066: The Twin Towers ★★★☆☆ 題組:Problem Set Archive with Online Judge
學習單元:N6 數的性質 學習單位:N6-3 用短除法求H.C.F. 和 L.C.M. 學習重點 : 1. 複習因數分解法求
數學 近似值 有效數值.
輸入&輸出 函數 P20~P21.
最大公因數 第 1 頁.
小學四年級數學科 8.最大公因數.
我喜歡英文中的中年代稱,不是 mid-age 這麼赤裸裸的直稱,而是用 prime time - 黃金時間
10465: Homer Simpson ★★★☆☆ 題組:Problem Set Archive with Online Judge
10949 : Kids in a Grid ★★★★☆ 題組:Problem Set Archive with Online Judge
基本IO.
五年級下學期 (一)200以內質數的判別.
10902: Pick-up Sticks ★★☆☆☆ 題組:Problem Set Archive with Online Judge
順德聯誼總會梁潔華小學 六年級 數學科 下學期 數形.
11413 : Fill the Containers ★★★★☆
士師記.
因數的世界 因數、公因數與最大公因數 朱曉萍編製.
10415: Eb Alto Saxophone Player
高年級整數教材教法分析 ~公因數、公倍數~ 林玉鴦
10115: Automatic Editing ★★☆☆☆
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
※歡迎挑戰,兩人(隊)中先完成連線即算過關!
11058: Encoding ★☆☆☆☆ 題組:Problem Set Archive with Online Judge
Commando War ★★☆☆☆ 題組:Problem Set Archive with Online Judge
if (j…) printf ("… prime\n"); else printf ("… not prime\n");
10328: Coin Toss ★★★☆☆ 題組:Problem Set Archive with Online Judge
674: Coin Change ★★☆☆☆ 題組:Problem Set Archive with Online Judge
1753: Need for Speed ★★☆☆☆ 題組:Problem Set Archive with Online Judge
1757: Secret Chamber at Mount Rushmore
13194: DPA Number II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
1730: Sum of MSLCM ★★☆☆☆ 題組:Problem Set Archive with Online Judge
11908: Skyscraper ★★★☆☆ 題組:Problem Set Archive with Online Judge
因數與倍數 【授課篇】 適用年級:5-6年級 設計者:MRI團隊.
因數與倍數.
10599: Robots(II) ★★★★☆ 題組:Problem Set Archive with Online Judge
10039: Railroads ★★☆☆☆ 題組:Problem Set Archive with Online Judge
11455: Behold My Quadrangle ★☆☆☆☆
All Sources Shortest Path The Floyd-Warshall Algorithm
10393:The One-Handed Typist
認識質數與合數 蔡瑞麟.
10107: What is the Median? ★★☆☆☆
1-3 最大公因數與最小公倍數.
10440: Ferry Loading II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
10791: Minimum Sum LCM ★★★☆☆ 題組:Problem Set Archive with Online Judge
11616:Roman Numerals ★★☆☆☆ 題組:Problem Set Archive with Online Judge
10489: Boxes of Chocolates ★★☆☆☆
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
12439: February 29 ★☆☆☆☆ 題組:Problem Set Archive with Online Judge
11506: Angry Programmer ★★★★☆ 題組:Contest Set Archive with Online Judge
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
11368: Nested Dolls ★★★☆☆ 題組:Problem Set Archive with Online Judge
10801: Lift Hopping ★★★☆☆ 題組:Problem Set Archive with Online Judge
1200: A DP problem ★★☆☆☆ 題組:Problem Set Archive with Online Judge
Presentation transcript:

10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge 解題者:經皓元 解題日期:2013年5月2日 題意:twin prime為相差2的質數對,如(3, 5), (5, 7)…等。題目輸入一個整數S, 1<=S<=100,000 ,輸出第S對質數對。

題意範例: 1  (3, 5) 2  (5, 7) 3  (11, 13) 100,000  (18409199, 18409210) 解法:建立質數表。因為第10萬對twin prime將超過1800萬, 若比較每個數是否能被其他數整除,將超過時限。 解法範例:以Sieve of Eratosthenes方法建立120以內的質數表作為範例。原理是消除所有的合數,剩下的就是質數。一個合數 x 必定有個小於等於 sqrt(x) 的質因數,若刪掉這些質數的倍數的倍數,就能刪掉所有合數了。 質數表建立完後掃過一遍建立twin prime表,之後依照 題目輸入輸出對應的twin prime。

從質數i的i倍開始消去的原因: 以7為例: 從7的7倍的倍數開始消去的原因: 7的2, 3, 5倍(質數倍):已經在之前的質數的倍數中消掉。 7的4, 6倍(合數倍):所有合數皆為小於它的質數的倍數,因此也在消去之前的質數的倍數中被消掉了。

判斷到質數7為止的原因: 120內的數若為合數,則必有一質因數小於等於sqrt(120) ≒ 10.95,因7為小於等於10.95中最大的質數,因此判斷到7就可以,之後沒有被消掉的數皆為質數。

討論: (1) 若用檢查因數的方法判斷質數,則時間複雜度為O(n^2) ,若改用Sieve of Eratosthenes判斷質數,時間複雜度變為O(n(logn)(loglogn)),以n = 2000萬來說,效率約差300萬倍