hdu 1239 找素數對

題意：給你一個大于4的整數m和一個真分數a/b，求最佳素數對p、q，使得a/b<=p/q<=1且pq<=m。最佳即為滿足條件的pair中pq最大的一對。

各種打表

zsd:素數的提取

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

<code>#include&lt;iostream&gt;</code>

<code>#include&lt;cstring&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

<code>int</code> <code>main() </code>

<code>{ </code>

<code>    </code><code>int</code>

<code>prime[2000],k; </code>

<code>num[10001]; </code>

<code>i,l; </code>

<code>t; </code>

<code>m; </code>

<code>    </code><code>double</code>

<code>a,b; </code>

<code>ro; </code>

<code>w,h; </code>

<code>max; </code>

<code>  </code> 

<code>    </code><code>memset</code><code>(num,0,</code><code>sizeof</code><code>(num)); </code>

<code>    </code><code>num[0]=num[1]=1; </code>

<code>    </code><code>k=0; </code>

<code>   </code><code>for</code><code>(i=2;i&lt;=10000;i++)</code>

<code>       </code><code>if</code><code>(num[i]==0)</code>

<code>       </code><code>{</code>

<code>           </code><code>for</code><code>(t=2*i;t&lt;=10000;t+=i)</code>

<code>               </code><code>num[t]=1;</code>

<code>           </code><code>prime[k]=i;</code>

<code>           </code><code>k++;</code>

<code>       </code><code>}</code>

<code>    </code><code>while</code><code>(cin&gt;&gt;m&gt;&gt;a&gt;&gt;b&amp;&amp;(m!=0||a!=0||b!=0))</code>

<code>   </code><code>{ </code>

<code>        </code><code>ro=a/b; </code>

<code>        </code><code>max=0;</code>

<code>        </code><code>for</code><code>(i=k-1;i&gt;=0;i--)</code>

<code>        </code><code>{</code>

<code>            </code><code>for</code><code>(l=i;l&gt;=0;l--)</code>

<code>            </code><code>{</code>

<code>                </code><code>if</code><code>(prime[i]*prime[l]&gt;m||(</code><code>double</code><code>)prime[l]/prime[i]&lt;ro) </code>

<code>                    </code><code>continue</code><code>;  </code>

<code>                </code><code>if</code><code>(prime[i]*prime[l]&gt;max)</code>

<code>                </code><code>{</code>

<code>                    </code><code>w=prime[l];</code>

<code>                    </code><code>h=prime[i];</code>

<code>                    </code><code>max=prime[i]*prime[l];</code>

<code>                </code><code>}</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>cout&lt;&lt;w&lt;&lt;</code><code>" "</code><code>&lt;&lt;h&lt;&lt;endl;</code>

<code>    </code><code>} </code>

<code>    </code><code>return</code>

<code>0; </code>

<code>} </code>