51nod 1106 质数检测(miller rabin 素数测试.)

1106 质数检测

基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题

收藏

关注

给出N个正整数,检测每个数是否为质数。如果是,输出"Yes",否则输出"No"。

Input

第1行:一个数N,表示正整数的数量。(1 <= N <= 1000)
第2 - N + 1行:每行1个数(2 <= S[i] <= 10^9)

Output

输出共N行,每行为 Yes 或 No。

Input示例

5
2
3
4
5
6

Output示例

Yes
Yes
No
Yes
No<br></br><br></br>miller rabin 素数测试...

 1<span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008000;">************************************************************************
 2</span><span style="color: #008080;"> 2</span> <span style="color: #008000;">    > File Name: code/51nod/1106.cpp
 3</span><span style="color: #008080;"> 3</span> <span style="color: #008000;">    > Author: 111qqz
 4</span><span style="color: #008080;"> 4</span> <span style="color: #008000;">    > Email: rkz2013@126.com 
 5</span><span style="color: #008080;"> 5</span> <span style="color: #008000;">    > Created Time: 2015年10月19日 星期一 18时51分06秒
 6</span><span style="color: #008080;"> 6</span> <span style="color: #008000;"> ***********************************************************************</span><span style="color: #008000;">*/</span>
 7<span style="color: #008080;"> 7</span> 
 8<span style="color: #008080;"> 8</span> #include<iostream>
 9<span style="color: #008080;"> 9</span> #include<iomanip>
10<span style="color: #008080;">10</span> #include<cstdio>
11<span style="color: #008080;">11</span> #include<algorithm>
12<span style="color: #008080;">12</span> #include<cmath>
13<span style="color: #008080;">13</span> #include<cstring>
14<span style="color: #008080;">14</span> #include<<span style="color: #0000ff;">string</span>>
15<span style="color: #008080;">15</span> #include<map>
16<span style="color: #008080;">16</span> #include<<span style="color: #0000ff;">set</span>>
17<span style="color: #008080;">17</span> #include<queue>
18<span style="color: #008080;">18</span> #include<vector>
19<span style="color: #008080;">19</span> #include<stack>
20<span style="color: #008080;">20</span> #include<cctype>
21<span style="color: #008080;">21</span>                  
22<span style="color: #008080;">22</span> <span style="color: #0000ff;">#define</span> yn hez111qqz
23<span style="color: #008080;">23</span> <span style="color: #0000ff;">#define</span> j1 cute111qqz
24<span style="color: #008080;">24</span> <span style="color: #0000ff;">#define</span> ms(a,x) memset(a,x,sizeof(a))
25<span style="color: #008080;">25</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;
26</span><span style="color: #008080;">26</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dx4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span>,<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span><span style="color: #000000;">};
27</span><span style="color: #008080;">27</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dy4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span>,<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span><span style="color: #000000;">};
28</span><span style="color: #008080;">28</span> typedef <span style="color: #0000ff;">long</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> LL;
29</span><span style="color: #008080;">29</span> typedef <span style="color: #0000ff;">double</span><span style="color: #000000;"> DB;
30</span><span style="color: #008080;">30</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> inf = <span style="color: #800080;">0x3f3f3f3f</span><span style="color: #000000;">;
31</span><span style="color: #008080;">31</span> 
32<span style="color: #008080;">32</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> witness(LL a,LL n)
33</span><span style="color: #008080;">33</span> <span style="color: #000000;"> {
34</span><span style="color: #008080;">34</span> <span style="color: #000000;">    LL t,d,x;
35</span><span style="color: #008080;">35</span>  d=<span style="color: #800080;">1</span><span style="color: #000000;">;
36</span><span style="color: #008080;">36</span>  <span style="color: #0000ff;">int</span> i=ceil(log(n-<span style="color: #800080;">1.0</span>)/log(<span style="color: #800080;">2.0</span>)) - <span style="color: #800080;">1</span><span style="color: #000000;">;
37</span><span style="color: #008080;">37</span>  <span style="color: #0000ff;">for</span>(;i>=<span style="color: #800080;">0</span>;i--<span style="color: #000000;">)
38</span><span style="color: #008080;">38</span> <span style="color: #000000;"> {
39</span><span style="color: #008080;">39</span>  x=d; d=(d*d)%<span style="color: #000000;">n;
40</span><span style="color: #008080;">40</span>  <span style="color: #0000ff;">if</span>(d==<span style="color: #800080;">1</span> && x!=<span style="color: #800080;">1</span> && x!=n-<span style="color: #800080;">1</span>) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
41</span><span style="color: #008080;">41</span>  <span style="color: #0000ff;">if</span>( ((n-<span style="color: #800080;">1</span>) & (<span style="color: #800080;">1</span><<i))> <span style="color: #800080;">0</span><span style="color: #000000;">)
42</span><span style="color: #008080;">42</span>  d=(d*a)%<span style="color: #000000;">n;
43</span><span style="color: #008080;">43</span> <span style="color: #000000;"> }
44</span><span style="color: #008080;">44</span>  <span style="color: #0000ff;">return</span> d==<span style="color: #800080;">1</span>? <span style="color: #0000ff;">false</span> : <span style="color: #0000ff;">true</span><span style="color: #000000;">;
45</span><span style="color: #008080;">45</span> <span style="color: #000000;"> }
46</span><span style="color: #008080;">46</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> miller_rabin(LL n)
47</span><span style="color: #008080;">47</span> <span style="color: #000000;"> {
48</span><span style="color: #008080;">48</span>  <span style="color: #0000ff;">if</span>(n==<span style="color: #800080;">2</span>) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
49</span><span style="color: #008080;">49</span>  <span style="color: #0000ff;">if</span>(n==<span style="color: #800080;">1</span> || ((n&<span style="color: #800080;">1</span>)==<span style="color: #800080;">0</span>)) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
50</span><span style="color: #008080;">50</span>  <span style="color: #0000ff;">for</span>(<span style="color: #0000ff;">int</span> i=<span style="color: #800080;">0</span>;i<<span style="color: #800080;">50</span>;i++<span style="color: #000000;">){
51</span><span style="color: #008080;">51</span>  LL a=rand()*(n-<span style="color: #800080;">2</span>)/RAND_MAX +<span style="color: #800080;">1</span><span style="color: #000000;">;
52</span><span style="color: #008080;">52</span>  <span style="color: #0000ff;">if</span>(witness(a, n)) <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;
53</span><span style="color: #008080;">53</span> <span style="color: #000000;"> }
54</span><span style="color: #008080;">54</span>  <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">true</span><span style="color: #000000;">;
55</span><span style="color: #008080;">55</span> <span style="color: #000000;"> }
56</span><span style="color: #008080;">56</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()
57</span><span style="color: #008080;">57</span> <span style="color: #000000;"> {
58</span><span style="color: #008080;">58</span>      
59<span style="color: #008080;">59</span>  <span style="color: #0000ff;">int</span><span style="color: #000000;"> n,cnt;
60</span><span style="color: #008080;">60</span> <span style="color: #000000;"> LL a;
61</span><span style="color: #008080;">61</span>  <span style="color: #0000ff;">while</span>(scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&n;)!=<span style="color: #000000;">EOF)
62</span><span style="color: #008080;">62</span> <span style="color: #000000;"> {
63</span><span style="color: #008080;">63</span>  cnt=<span style="color: #800080;">0</span><span style="color: #000000;">;
64</span><span style="color: #008080;">64</span>  <span style="color: #0000ff;">while</span>(n--<span style="color: #000000;">)
65</span><span style="color: #008080;">65</span> <span style="color: #000000;"> {
66</span><span style="color: #008080;">66</span>  scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%lld</span><span style="color: #800000;">"</span>,&<span style="color: #000000;">a);
67</span><span style="color: #008080;">67</span>  <span style="color: #0000ff;">if</span><span style="color: #000000;">(miller_rabin(a))
68</span><span style="color: #008080;">68</span>  puts(<span style="color: #800000;">"</span><span style="color: #800000;">Yes</span><span style="color: #800000;">"</span><span style="color: #000000;">);
69</span><span style="color: #008080;">69</span>  <span style="color: #0000ff;">else</span> 
70<span style="color: #008080;">70</span>      puts(<span style="color: #800000;">"</span><span style="color: #800000;">No</span><span style="color: #800000;">"</span><span style="color: #000000;">);
71</span><span style="color: #008080;">71</span> <span style="color: #000000;"> }
72</span><span style="color: #008080;">72</span> <span style="color: #008000;">//</span><span style="color: #008000;"> printf("%dn",cnt);</span>
73<span style="color: #008080;">73</span> <span style="color: #000000;"> }
74</span><span style="color: #008080;">74</span>  <span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;
75</span><span style="color: #008080;">75</span>  }

View Code