首页 > 代码库 > Eratosrhenes筛选法

Eratosrhenes筛选法

2024-07-14 12:23:09   225人阅读

 

1简介

     埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。

2步骤

（1）先把1删除（现今数学界1既不是质数也不是合数）
（2）读取队列中当前最小的数2，然后把2的倍数删去
（3）读取队列中当前最小的数3，然后把3的倍数删去
（4）读取队列中当前最小的数5，然后把5的倍数删去
（5）如上所述直到需求的范围内所有的数均删除或读取
注：此处的队列并非数据结构队列，如需保留运算结果，处于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。
 
该算法是用空间换时间，代码实现如下
#include <stdio.h>#include <stdlib.h>#define SIZE 10000#define TRUE 1#define FALSE 0intmain(){char sieve[ SIZE ]; /* the sieve */char *sp; /* pointer to access the sieve */int number; /* number we’re computing *//*** Set the entire sieve to TRUE.*/for( sp = sieve; sp < &sieve[ SIZE ]; )*sp++ = TRUE;/*Solution 6.4 continued . . .Pointers on C—Instructor′s Guide 33** Process each number from 3 to as many as the sieve holds. (Note: the** loop is terminated from inside.)*/for( number = 3; ; number += 2 ){/*** Set the pointer to the proper element in the sieve, and stop** the loop if we’ve gone too far.*/sp = &sieve[0]+(number-3) / 2;if( sp >= &sieve[ SIZE ] )break;/*** Now advance the pointer by multiples of the number and set** each subsequent entry FALSE.*/while( sp += number, sp < &sieve[ SIZE ] )*sp = FALSE;}/*** Go through the entire sieve now and print the numbers corresponding** to the locations that remain TRUE.*/number=2;printf( "%8d", number );for( number = 3, sp = &sieve[ 0 ];sp < &sieve[ SIZE ];number += 2, sp++ ){if( *sp )printf( "%8d", number );}return EXIT_SUCCESS;}

　由于除了2之外，所有偶数都不是质数，所以令数组中的元素只对应奇数，可使程序的空间效率提高一倍。

n（数组下标）　0　　1　　2　　3　　4　　5　　6　　7　　8　　9　　10

s（奇数）　　   3　　5　　7　　9　  11　13　  15    17    19    21    23

显然s=2*n+3    由于n增加1时，s增加2.

所以对s进行筛选时

读取3，然后将2*3=6的倍数删去（因为是对奇数进行筛选）——》对n将3k+0的数删去

所以对下标n进行筛选时，可删去3k，1+5k，2+7k。。。。。

for( number = 3; ; number += 2 ){/*** Set the pointer to the proper element in the sieve, and stop** the loop if we’ve gone too far.*/sp = &sieve[0]+(number-3) / 2;if( sp >= &sieve[ SIZE ] )break;/*** Now advance the pointer by multiples of the number and set** each subsequent entry FALSE.*/while( sp += number, sp < &sieve[ SIZE ] )*sp = FALSE;}


联系
我们