华师一附中OI组

标题: 筛法求质数 [打印本页]

---

作者: admin    时间: 2019-1-6 20:15
标题: 筛法求质数
筛法求质数的流程：假设求2-100之间的所有质数
1、把2-100之间的所有数写在纸上。（对应编程的做法就是a数组中a(2)-a(100)全部设为1）
2、从2到100，若这个数是质数，那么把它的2倍，3倍，直到不超过100的所有倍数全部刷掉；若不是，则直接跳到下一个数。           用i表是这个数，则刷掉它的倍数可以用类似开关灯的方法来做，两种写法。
3、检查纸上的数字若没有被刷掉，表示是质数，则输出（对应编程的做法就是检查a(2)-a(100)，若为1则输出对应的下标）
把上面的解释转换成程序：
1、for (i=2;i<=100;i++) a(i)=1;
2、for (j=i+i;j<=100;j++) a(j)=0;或者for (j=i+1;j<=100;j++) if (j%i==0) a[j]=0;   显然第一种更好。
3、for (i=2;i<=100;i++) if (a(i)==1) cout<<j<<' ';


合成为完整的程序：

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=100;
   
4. bool a[mn+5];
   
5. int i,j;
   
6. int main()
   
7. {
   
8.         for (i=2; i<=mn; i++) a[i]=1;
   
9.         for (i=2; i<=mn; i++)
   
10.                 if (a[i]==1)  for (j=i*2; j<=mn; j+=i) a[j]=0;
    
11.         for (i=2; i<=mn; i++) if (a[i]==1) cout<<i<<' ';
    
12.         return 0;
    
13. }

复制代码

---

作者: admin    时间: 2020-2-11 14:51
象楼上那样做是比较简单清晰的，效率还可以提高，
1、j没有必要从i*2开始，因为i*2可能已经被2刷掉了，i*3可能已经被3刷掉了
2、i的终点没有必要到mn，后面的一些其实早就被刷掉了两者的共同理由是若x=a*b，则x肯定先被a和b中较小数刷掉，那么第一个问题中的j只需要从i*i开始就可以了，第二个问题中的i只需要到sqrt(i)就可以了。

1. #include <iostream>
   
2. using namespace std;
   
3. const int mn=100;
   
4. bool a[mn+5];
   
5. int i,j;
   
6. int main()
   
7. {
   
8.         for (i=2; i<=mn; i++) a[i]=1;
   
9.         for (i=2; i*i<=mn; i++) ///i<=sqrt(mn)
   
10.                 if (a[i]==1)  for (j=i*i; j<=mn; j+=i) a[j]=0;
    
11.         for (i=2; i<=mn; i++) if (a[i]==1) cout<<i<<' ';
    
12.         return 0;
    
13. }

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2