弄了个欧拉筛求素数~ - C语言论坛

楼主

问题点数：0 回复次数：3

弄了个欧拉筛求素数~

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

程序代码：

#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;
}

搜索更多相关主题的帖子: assert　void　int　NULL　for　

第 2 楼

得分:0

支持一下！

普通人之所以普通，是因为他们普遍有一个通病，那就是认为自己永远普通。
千夫所指，我亦坚持。就算被所有人误解，我也照样守护这一切。
我们总是觉得，这些灵魂的表情，傲慢自大，目中无人，其实，真正目中无人的是我们。它们傲慢的不过是表情，而我们傲慢的却是行为！
记得，是为了忘记！
只要想着有那么一天，我就能忍受现在的每一天！
灾难并不可怕，可怕的是心中没有了希望。
你以为我在天堂，其实我正在路上。
当你觉得自己走不到终点的时候，请不要放弃。或许你的对手也是这种感觉。

第 3 楼

得分:0

做个标记

第 4 楼

得分: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编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]