欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

利用Eratosthenes筛选法计算质数

程序员文章站 2024-03-21 15:27:46
...

       算法第1步就是写下从3至某个上限之间的所有奇数。在算法的剩余部分,遍历整个列表并剔除所有不是质数的奇数。在3之后把每逢第3个数(3的倍数)剔除。完成这一步之后,轮到5,将所有5的倍数剔除。这样依次类推、反复进行,最后列表中未被剔除的数均为质数。

      这里可能读者会有问题了,为什么轮到4、6、8、10等等之类的数字呢?原因在于,我们待筛选的列表中的所有数字都是奇数。一开始就直接从奇数空间寻找质数(偶数除2之外都不是质数),那么用4、6、8、10之类的数字作为标准参与剔除过程是不必要的,奇数和这类数字肯定没有公约数。自然筛选完成之后是没有发生改变的。

      这样可能还是比较抽象,我将用一张示意图进行说明:

利用Eratosthenes筛选法计算质数

红色标记代表已经被剔除

        每个数组元素的值用于标记对应的数是否已被剔除。开始时所有元素的值都设置为TRUE(值为1),当算法要求“剔除”其对应的数字时,就把这个元素设置为FALSE(值为0)。

       以上处理都完成了之后,准备输出列表中的数字,注意,列表只是一个逻辑概念,并不真实存在,所以用本算法会使得程序的空间效率大大提高。并不是列表中的任意数字都能输出的,只有该数字对应的数组元素的值为TRUE是才能够输出

      我们回顾一下传统的找寻质数的办法,最大的缺陷就是把所有待筛选的数字都放在数组里面,并没有充分利用下标,大大浪费了空间。

#define SIZE 20
#define TRUE 1
#define FALSE 0
#include<stdio.h>
 
int main() {
	char sieve[SIZE];
	char *sp;
	int number;
	for (sp = sieve; sp < &sieve[SIZE];)
		*sp++ = TRUE;
	for (number = 3;; number += 2) {
		sp = &sieve[0] + (number - 3) / 2;
		if (sp >= &sieve[SIZE])
			break;
		while (sp += number, sp < &sieve[SIZE])
			*sp = FALSE;
	}
	printf("2\n");
	for (number = 3, sp = &sieve[0];
		sp < &sieve[SIZE];
		number += 2, sp++) {
		if (*sp)
			printf("%d\n", number);
	}
	return 0;
}
利用Eratosthenes筛选法计算质数

本程序在VS2017下运行通过,环境不同可能会造成困扰。