首页 > 其他 > 详细

筛法列举质数

时间:2017-08-25 16:43:17      阅读:238      评论:0      收藏:0      [点我收藏+]

思想:标记出所有非质数,输出所有未被标记的数。

对于n以内的筛选来说,如果n是合数,则有 1 ≤ c ≤ √n ,即 1 ≤ c2 ≤ n , c是n的最小正因数。只要找到了c就可以确定n是合数并将n标记。

技术分享
1     int n = 15;
2     int mark[16] = {
3         1, 1, 0, 0,
4         0, 0, 0, 0,
5         0, 0, 0, 0,
6         0, 0, 0, 0
7     };
View Code

设n = 15,先声明一个数组mark,里面除了0和1被标记为1(即为false)之外,别的都未被标记。已知2为最小的质数,所以我们让2作为第一个正因数,开始筛选,筛选完后输出15以内的所有质数:

 1     int c;
 2     int j;
 3     for (c = 2; c * c <= n; c++) {
 4         if (mark[c] != 1) {
 5             for (j = 2; j <= n / c; j++) {
 6                 mark[c * j] = 1;
 7             }
 8         }
 9     }
10     for (c = 2; c <= n; c++) {
11         if (mark[c] != 1) {
12             printf("%d\n", c);
13         }
14     }

 伪代码:

1 function Eratosthenes
2     Let A be an array of Boolean values,
3     indexed by integers 2 to n
4     initially all set to true.
5     for index from 2 to sqrt(n)
6         if A[i] is true
7             for j from 2 to n/index
8                 A[j] = false
9     Output: all i such that A[i] is true

 

筛法列举质数

原文:http://www.cnblogs.com/xudongwei/p/7428542.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!