注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

信息 灵感 创新

III = Information,Inspiration,Innovation

 
 
 

日志

 
 
关于我

we are 5. Mathematics, Computation, Programming, Engineering, and Making fun of life.

网易考拉推荐

C程序:查找前n个质数  

2017-10-15 16:04:35|  分类: C & C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
void ListNPrimes(unsigned int n)
{
    unsigned long long *pPrimes=NULL;
    unsigned long long test;
    unsigned int cnt,i,primeFlag,sqrt_test;
    if(n<4)
    {
        printf("ListNPrimes:\"n\" should be no less than 4.\n");
        return;
    }

    pPrimes=(unsigned long long*)calloc(n,sizeof(unsigned long long));
    if(!pPrimes)
    {
        printf("ListNPrimes:Memory allocation failed.\n");
        return;
    }
    *pPrimes=2UL;
    *(pPrimes+1)=3UL;
    *(pPrimes+2)=5ULL;
    cnt=3;
    test=5;
    while(cnt<n)
    {
        test+=2;
        if((test-1)%6!=0&&(test+1)%6!=0)
            continue;
        primeFlag=1;
        sqrt_test=(unsigned int)sqrt(test);
        for(i=1;i<cnt;i++)
        {
            if(*(pPrimes+i)>sqrt_test)
                break;
            if(test%*(pPrimes+i)==0)
            {
                primeFlag=0;
                break;
            }
        }
        if(primeFlag)
        {
            *(pPrimes+cnt)=test;
            cnt++;
        }
    }
    for(i=0;i<n;i++)
    {
        printf("%12llu",*(pPrimes+i));
        if((i+1)%5==0)
            printf("\n");
    }
    free(pPrimes);
    pPrimes=NULL;
}
使用了动态内存分配,以及两个关于质数的属性:
1. 如果一个数是质数(除去2),则一定可以表示为6k+1 或者6k-1的形式,所以不满足这种形式的数,肯定不是质数;
2. 一个数n,如果不能被不超过其sqrt(n)的质数整除,则一定是质数。
  评论这张
 
阅读(27)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017