素数的线性筛法
//整体思想是从自然数 2 开始与所有之前已经确定的素数相乘后的数标记为合数就能把素数一个不漏地找出来
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define FORD(i,s,t) for(int i=(s-1); i>=t; i--)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)
using namespace std;
const int SULEN = 1000000;
bool flag[SULEN+1];// 是否为素数
int prime[1000001];// 存储的素数
int sum[SULEN+1];//n 的所有质因子的和
void xianxingshai(void)
{
int count,i,j;
fill( flag,flag+SULEN,true ); // 初始化假设每个都为素数
fill( sum ,sum +SULEN, 0 ); //初始化质因子和为0
flag[0] = flag[1] = false; //0 和 1 不是素数
for( count = 0, i = 2; i <= SULEN; i++ )// 从 2 开始判断是否为素数
{
if( flag[i] ) // 如果是素数
{
prime[count++] = i;sum[i] = i; //将值传到prime 数组中
}
for( j = 0; j < count && i*prime[j] <= SULEN; j++ ) // 将包含该质因数的合数都
标为
false
{
}
flag[ i*prime[j] ] = false;
if( i%prime[j] == 0 ) // 欧拉函数原理
{
sum[ i*prime[j] ] = sum[i]; break;
}
else sum[ i*prime[j] ] = sum[ i ] + prime[j];
}
}
}
int judgeprime(int n)
{
int i;
for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
return 1;
}
}
return 0;
}
int main(int argc, char *argv[])
{
int i;
xianxingshai();
for(i=0;i<10;i++) // 输出前10 个质数
{
printf("%d ",prime[i]);
}
return 0;。