This repository was archived by the owner on Apr 22, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path0018.html
More file actions
142 lines (141 loc) · 10.9 KB
/
0018.html
File metadata and controls
142 lines (141 loc) · 10.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
<meta content="text/html; charset=utf-8" http-equiv="Content-Type" />
<meta content="Word.Document" name="ProgId" />
<meta content="Microsoft Word 11" name="Generator" />
<meta content="Microsoft Word 11" name="Originator" />
<link href="file:///C:\DOCUME~1\DEFEND~1\LOCALS~1\Temp\msohtml1\01\clip_filelist.xml" rel="File-List" /><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:ApplyBreakingRules />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><style type="text/css">
<!--
/* Font Definitions */
@font-face
{font-family:"Angsana New";
panose-1:2 2 6 3 5 4 5 2 3 4;
mso-font-charset:0;
mso-generic-font-family:roman;
mso-font-pitch:variable;
mso-font-signature:16777219 0 0 0 65537 0;}
@font-face
{font-family:TTE18DB2C0t00;
panose-1:0 0 0 0 0 0 0 0 0 0;
mso-font-alt:"MS Mincho";
mso-font-charset:128;
mso-generic-font-family:auto;
mso-font-format:other;
mso-font-pitch:auto;
mso-font-signature:1 134676480 16 0 131072 0;}
@font-face
{font-family:"\@TTE18DB2C0t00";
panose-1:0 0 0 0 0 0 0 0 0 0;
mso-font-charset:128;
mso-generic-font-family:auto;
mso-font-format:other;
mso-font-pitch:auto;
mso-font-signature:1 134676480 16 0 131072 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-parent:"";
margin:0cm;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
mso-bidi-font-size:14.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Angsana New";}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;
mso-header-margin:36.0pt;
mso-footer-margin:36.0pt;
mso-paper-source:0;}
div.Section1
{page:Section1;}
/* List Definitions */
@list l0
{mso-list-id:348414556;
mso-list-type:hybrid;
mso-list-template-ids:38861868 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
-->
</style><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->
<p style="" class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ตระแกรงร่อนของอีราโทสเธเนส เป็นอัลกอริทึมที่ให้หาจำนวนเฉพาะจนถึงจำนวนนับ </span><span style="font-size: 14pt; font-family: "Angsana New";">N<span lang="TH"> วิธีการมีดังนี้</span><o:p></o:p></span></p>
<p style="margin-left: 36pt; text-indent: -18pt;" class="MsoNormal"><!--[if !supportLists]--><span style="font-size: 14pt; font-family: "Angsana New";"><span style="">1.<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none;"> </span></span></span><!--[endif]--><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">เขียนจำนวนนับตั้งแต่ </span><span style="font-size: 14pt; font-family: "Angsana New";">2 <span lang="TH">จนถึง </span>N<span lang="TH"> ทั้งหมด</span><o:p></o:p></span></p>
<p style="margin-left: 36pt; text-indent: -18pt;" class="MsoNormal"><!--[if !supportLists]--><span style="font-size: 14pt; font-family: "Angsana New";"><span style="">2.<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none;"> </span></span></span><!--[endif]--><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">หาจำนวนที่<b>น้อยที่สุด</b>ที่ยังไม่ถูกขีดค่า และเราให้จำนวนนั้นคือ </span><span style="font-size: 14pt; font-family: "Angsana New";">P <span lang="TH">(</span>P <span lang="TH">คือจำนวนเฉพาะ)</span><o:p></o:p></span></p>
<p style="margin-left: 36pt; text-indent: -18pt;" class="MsoNormal"><!--[if !supportLists]--><span style="font-size: 14pt; font-family: "Angsana New";"><span style="">3.<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none;"> </span></span></span><!--[endif]--><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ขีดค่าจำนวนที่เป็นพหุคูณของ </span><span style="font-size: 14pt; font-family: "Angsana New";">P <span lang="TH">ทุกตัว<b>ที่ยังไม่ถูกขีดค่า</b></span><o:p></o:p></span></p>
<p style="margin-left: 36pt; text-indent: -18pt;" class="MsoNormal"><!--[if !supportLists]--><span style="font-size: 14pt; font-family: "Angsana New";"><span style="">4.<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none;"> </span></span></span><!--[endif]--><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ถ้ายังคงมีจำนวนนับที่ยังไม่ถูกขีดค่า ให้กลับไปทำขั้นตอนที่ </span><span style="font-size: 14pt; font-family: "Angsana New";">2<o:p></o:p></span></p>
<p style="" class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">โจทย์</span></u></b><b><u><span style="font-size: 14pt; font-family: "Angsana New";"><o:p></o:p></span></u></b></p>
<p style="" class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">จงเขียนโปรแกรมที่รับจำนวนเต็ม </span><span style="font-size: 14pt; font-family: "Angsana New";">N, K<span lang="TH"> ให้หาว่า จำนวนตัวที่ </span>K <span lang="TH">ที่ถูกขีดค่า คือจำนวนใด</span><o:p></o:p></span></p>
<p style="" class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ข้อมูลนำเข้า</span></u></b><b><u><span style="font-size: 14pt; font-family: "Angsana New";"><o:p></o:p></span></u></b></p>
<p style="" class="MsoNormal"><b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">บรรทัดแรก</span></b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";"> จำนวนเต็ม </span><span style="font-size: 14pt; font-family: "Angsana New";">N <span lang="TH">และ </span>K <span lang="TH">โดยที่ </span>(2 <= K < N <= 1,000)<o:p></o:p></span></p>
<p style="" class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ข้อมูลส่งออก</span></u></b><b><u><span style="font-size: 14pt; font-family: "Angsana New";"><o:p></o:p></span></u></b></p>
<p style="" class="MsoNormal"><b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">บรรทัดแรก</span></b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";"> จำนวนตัวที่ </span><span style="font-size: 14pt; font-family: "Angsana New";">K <span lang="TH">ที่ถูกขีดค่านับแต่เริ่มต้นอัลกอริทึม</span><o:p></o:p></span></p>
<p style="" class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">อธิบายตัวอย่างที่สาม (ด้านล่าง)</span></u></b><b><u><span style="font-size: 14pt; font-family: "Angsana New";"><o:p></o:p></span></u></b></p>
<p style="" class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ลำดับจำนวนตัวเลขที่ถูกขีดค่าคือ</span><span style="font-size: 14pt; font-family: "Angsana New";"><o:p></o:p></span></p>
<p style="" class="MsoNormal"><span style="font-size: 14pt; font-family: "Angsana New";">2, 4, 6, 8, 10, 3, 9, 5 <span lang="TH">และ </span>7<o:p></o:p></span></p>
<p style="" class="MsoNormal"><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">และจำนวนที่ </span></u><u><span style="font-size: 14pt; font-family: "Angsana New";">7 <span lang="TH">ที่ถูกขีดค่าคือ </span>9<o:p></o:p></span></u></p>
<p style="" class="MsoNormal"><span style="font-size: 14pt; font-family: "Angsana New";"><o:p> </o:p></span></p>
<p style="" class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ที่มา</span></u></b><b><u><span style="font-size: 14pt; font-family: "Angsana New";">:</span></u></b><b><span style="font-size: 14pt; font-family: "Angsana New";"> <strong><span style="font-family: "Angsana New";">COCI 2008/2009, Contest #2 – November 15, 2008<o:p></o:p></span></strong></span></b></p>
<table>
<tr>
<th>ข้อมูลนำเข้า</th>
<th>ข้อมูลส่งออก</th>
</tr>
<tr>
<td>7 3
<br /></td>
<td>6</td>
</tr>
<tr>
<td>15 12</td>
<td>7</td>
</tr>
<tr>
<td>10 7</td>
<td>9</td>
</tr></table>