素数的生成和计数的几种算法
veekxt 发布于 2015-07-02 15:45:28

记录几种素数的生成算法,这里有1000万以内的素数表,大,慎点

基本算法

根据素数的定义,逐个检查是否能被别的数整除。


//输出min到n之间的素数,并返回个数
int printsu_1(int min,int n)
{
    int count=0;
    for(int j=min; j<=n; j++)
    {
        int i=2;
        for(; i<j; i++)
        {
            if(j%i==0)//举个判断。
            {
                break;
            }
        }
        if(j==i)
        {
            printf("%d ",j);
            count=count+1;
        }
    }
    return count;
}

改进的基本算法

因为一个数的因子必然小于它的平方根,所以只要判断到sqrt(n)即可。


//输出min到n之间的素数,并返回个数
int printsu_2(int min,int n)
{
    int count=0;
    for(int j=min; j<=n; j++)
    {
        int i=2;
        int max_i=sqrt(j);
        for(; i<=max_i; i++)//缩小了判断次数
        {
            if(j%i==0)
            {
                break;
            }
        }
        if(max_i+1==i)
        {
            printf("%d ",j);
            count=count+1;
        }
    }
    return count;
}
//也可以封装一个判断函数,判断是否为素数,遍历调用
int issu(int n)
{
	if(n<2)return 0;
	int i=2;
	int max_i=sqrt(j);
	for(; i<=max_i; i++)
	{
		if(j%i==0)
		{
			break;
		}
	}
	
	if(max_i+1==i)
	{
		return 1;
	}
	
	return 0;
}

筛法

筛法的基本思想是在一个顺序的数列中,逐渐筛去合数,比如一个数列
2,3,4,5,6,7,8,9,10
先去掉2的倍数4,6,8,10,
2,3,5,7,9
再去掉3的倍数6,9,
2,3,5,7
。。。。。。
一般设置一个数组,开始初始化为1标记全为素数,然后把要去除的数对应的下标置为0,标记为合数,比如第一轮把arr[4],arr[6]...置为0。


//n以内的素数,并返回个数
int printsu_4(int n)
{
    n=n+1;
    int count=0;
    int *arr = (int *)malloc(sizeof(int)*(n));
    for(int i=0; i<n; i++)
    {
        arr[i]=1;
    }
    arr[0]=0;
    arr[1]=0;
    for (int i=2;  i<=sqrt(n);  i++)
        if (arr[i])
        {
            for (int k=i*i; k<n; k+=i)//小小的优化,把初值设为i*i
                arr[k]=0;
        }
    for(int k=0; k<n; k++)
    {
        if(arr[k]==1)
        {
            printf("%d ",k);
            count++;
        }
    }
    return count;
}

//初值不是二,输出min-n的素数。

int printsu_3(int min,int n)
{
    int count=0;
    int *arr = (int *)malloc(sizeof(int)*(n-min+1));
    for(int i=0; i<=n-min; i++)
    {
        arr[i]=1;
    }
    int max_i=sqrt(n);//筛子的最大值
    for(int i=2; i<=max_i; i++)
    {
        int min_j;
        if(min<=i)min_j=2;
        else if(min%i!=0)min_j=min/i+1;
        else min_j=min/i;
        if(min_j<i)min_j=i;
        for(int j=min_j; j<=n/i; ++j)
        {
            arr[i*j-min]=0;
        }
    }
    for(int k=0; k<=n-min; k++)
    {
        if(arr[k]==1)
        {
            printf("%d ",k+min);
            count=count+1;
        }
    }
    return count;
}

改进的筛法

上面的筛法优化空间在于它重复排除了很多数,比如2*n包含了所有的4*n,改进后每个数字仅被排除一次,它利用了所有合数都有素因子的特性。 一个完整的程序:


//统计100000000以内素数个数
#include<stdio.h>
#include<stdlib.h>

const long MAXP = 100000000;
long prime[MAXP] = {0},num_prime = 0;//保存已产生的素数数组
int isNotPrime[MAXP] = {1, 1};//排除合数数组
int main()
{
    int mycount=0;
    for(long i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++]=i;
        for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))
            {
                break;//注意这里的break
            }
        }
    }
    printf("%d",num_prime);
    return 0;
}

实际应用中的方法

实际中,需要素数的场合一般不会用程序产生,而是直接存放在内存或一个文件中,需要的时候直接读取就可以了,这也是空间换时间(?)的做法。