最近遇到某方面的内容和欧拉筛有关系,于是就自己重新弄了个欧拉筛,当然记得以前自己曾经写过一次,这次自己完全写起来发现和第一次写的主体方面还是差不多(就那么一个细微的区别),可以参考一下~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

void nodeMal( void** ,size_t );
void nodeFree( void** );
void nodeRea( void** ,size_t );

void fun ( char**,size_t**,size_t );
void print( const size_t* );

int main( void )
{
    char* isPrime=NULL;
    size_t* prime=NULL;

    fun(&isPrime,&prime,101);
    print(prime);
    
    nodeFree(( void** )&isPrime);
    nodeFree(( void** )&prime);
    
    return 0;
}

void nodeMal( void** p,size_t size )
{
    assert(p);
    
    *p=malloc(size);
    
    assert(*p);

    memset(*p,0,size);
}

void nodeRea( void** p,size_t size )
{
    void* p_new=NULL;
    
    assert(p);
    
    p_new=realloc(*p,size);
    
    assert(p_new);

 
     *p=p_new;
}

void nodeFree( void** p )
{
    assert(p);
    
    free(*p);
    *p=NULL;
}

void fun ( char** _isPrime,size_t** _prime,size_t len )
{
    
    char* isPrime=NULL;
    size_t* prime=NULL;
    
    size_t i;
    
    if (len<3)
        return ;
    
    nodeMal(( void** )_isPrime,sizeof (isPrime)*len);
    nodeMal(( void** )_prime,sizeof (isPrime)*len);
    
    isPrime=*_isPrime;
    prime=*_prime;
    
    for (i=0;i!=len;++i)
        isPrime[i]=0;  //测试手机运调用memset后可能还有少量内存块没有清零,所以这里重新赋值保险一点
        
    prime[0]=0;
    
    for (i=2;i!=len;++i)
    {
        size_t j;

        if (isPrime[i]==0)
            prime[++prime[0]]=i;
       
        for (j=1;prime[j]<=len/i;++j)
        {
            isPrime[i*prime[j]]=1;
            
            if (i%prime[j]==0)
                break;
        }
    }

    nodeRea(( void** )_prime,sizeof ( size_t )*((*_prime)[0]+1));
    
}

void print( const size_t* prime )
{
    size_t i;
    if (prime==NULL)
        return ;

    for (i=1;i!=prime[0]+1;++i)
        printf("%-6u",( unsigned )prime[i]);
        
    puts("");
}

PS:如果需要简单版参考的可以看看这个我第一次弄的(的确除了那个细节地方差不多一个样)~

#include<stdio.h>

#define MAX 100
char IsPrime[MAX+1]={0};
int prim[MAX+1]={0};

int main()
{
    int i=0;
    int j=0;
    int num=0;

    for (i=2;i<=MAX;++i)
    {
        if (!IsPrime[i])
            prim[num++]=i;

        for (j=0;j<num&&i*prim[j]<=MAX;++j)
        {
            IsPrime[i*prim[j]]=1;

            if (i%prim[j]==0)
                break;
        }
    }

    for (i=0;i<num;++i)
        printf("%-4d",prim[i]);

    puts("");

    return 0;
}

在用欧拉筛求素数其实还有两个可以解决的问题~
第一个是求欧拉函数~
还有另一个是求因子数~

PS:还有第三个分解质因式也是可以欧拉函数构建树状数组来简单实现的~

现在尝试了一下用欧拉筛求比n小的正整数的因子分别有多少个,例如6有1 2 3 6共4个因子,9有1 3 9共3个因子,其中写法和欧拉函数比较相似(有种相通的感觉,或者我可以试试把欧拉函数也弄出来,因为欧拉函数在求某些关于质数题目的时候起到至关重要的作用的)~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdarg.h>

void nodeMal( void** ,size_t );
void nodeFree( void** );

void freeAll( size_t,... );

void fun ( unsigned**,size_t );
void print( const unsigned* );

int main( void )
{
    
    size_t* factor=NULL;

    fun(&factor,101);
    print(factor);
    
    nodeFree(( void** )&factor);
    
    return 0;
}

void nodeMal( void** p,size_t size )
{
    assert(p);
    
    *p=malloc(size);
    
    assert(*p);

    memset(*p,0,size);
}

void nodeFree( void** p )
{
    assert(p);
    
    free(*p);
    *p=NULL;
}

void fun ( unsigned** _factor,size_t len )
{
    size_t* factor=NULL;
    
    char* isPrime=NULL;
    
    size_t* prime=NULL;
    
    size_t i;
    
    if (len<2)
        return ;
    
    nodeMal(( void** )_factor,sizeof
(*factor)*len+1);

    factor=*_factor;
    
    factor[0]=len;
    factor[1]=1;
    
    nodeMal(( void** )&isPrime,sizeof (*isPrime)*len);
    nodeMal(( void** )&prime,sizeof (*prime)*len);
    
    prime[0]=0;
    
    for (i=0;i!=len;++i)
        isPrime[i]=1; 
    
    for (i=2;i!=len;++i)
    {
        size_t j;

        if (isPrime[i])
        {
            factor[i]=2;
            prime[++prime[0]]=i;
        }
       
        for (j=1;prime[j]<=len/i;++j)
        {
            const size_t t=i*prime[j];
            
            factor[t]=factor[i]<<1;
            isPrime[t]=0;
             
            if (i%prime[j]==0)
             {
                factor[t]-=factor[i/prime[j]];
             
                 break;
             }
        }
    }
    
    freeAll(2,&isPrime,&prime);
    /*这里当时是多个标记数组的,是有3个参数的,不过后来优化发现其中一个可以不需要然后删了,还是保留一下函数可变参数的简单用法吧*/
}

void freeAll( size_t len,...)
{
    va_list ap;
    
    size_t i;
    
    va_start(ap,len);
   
    for (i=0;i!=len;++i)
    {
         void** t=va_arg(ap,void**);
         
         nodeFree(t);
    }    
    
    va_end(ap);
}

void print( const unsigned* factor )
{
    size_t i;
    if (factor==NULL||factor[0]==0)
        return ;

    for (i=1;i!=factor[0];++i)
        printf("%u:%u\n",( unsigned )i,factor[i]);
}

[此贴子已经被作者于2018-4-2 22:08编辑过]