素数筛（python、C）

一般筛法

例如要求N以内（不含N）的所有素数，初始化一个下标直到N-1的列表p，元素均赋值为1。下标代表数字，值为1/0代表是/否为素数。从2开始，列表里它的倍数都非素数，于是把它们赋值0，不再参与运算。之后是3、5（4、6被2消掉了）、7…以此类推。

python：

#通过构造素数表,找到小于n的所有素数 n=100 p=[1]*n#下标代表数字(0,1是合数不用管),值1/0代表是否为素数 for i in range(2,n): if p[i]==1: print("%d\t"%i,end='') k=i #注意这里 while i*k<n: p[i*k]=0 k+=1

C：

#include<stdio.h> #define N 500000 int main() { int p[N]={1,1},k; //利用c的列表中未初始化元素用0补全,省掉了赋值步骤.现在p中1代表合数,0代表质数 for(int i=2;i<N;i++) { if(p[i]==0) { printf("%d\n",i); for(unsigned long k=i;i*k<N;k++)//注意这里 p[i*k]=1; } } return 0; }

要注意的那个地方是个小改进，让k从i开始而不是从2开始，这样之前的素数已经删过的数就不再重复计算了（例如2*5已经排除了10，不需要再算5*2）。

快速筛法

使用上边一般筛法还是有重复计算，例如30在2、3、5循环时都被算出来过（2*15、3*10、5*6），而快速筛法没有这种缺点。这是无重复时的排除步骤⬇

最省事的还是打表((

快就完了。。

#include <stdio.h> int main() { int x,i; scanf("%d",&x); int a[]={素数粘这里}; while(a[i]<x) { printf("%d\t",a[i]); i++; } return 0; }