| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2686 人关注过本帖
标题:求素数的个数,出现未输入就退出程序的问题,求指点。谢谢~
只看楼主 加入收藏
Orcaina
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2016-10-18
收藏
得分:0 
回复 8楼 九转星河
我的算法不对
2016-10-25 18:35
Orcaina
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2016-10-18
收藏
得分:0 
回复 5楼 九转星河
拖延症晚期来报道:
/* 按照我之前的思路做,只能先求出1~a之间的素数个数,再求出1~b之间的素数个数,然后将两者相减得到结果,这样做将1~a之间的过程
重复计算了两次,不是很好
换一种思路是利用筛法先将所有素数球出来,然后再判断a~b之间有多少个素数
*/
第一种求法:
#include <stdio.h>
#include <math.h>

int c[1000001];
int main()
{
    int K,i,j,t;//k是案例个数
    int a,b;
    scanf("%d",&K);

    //输入a和b的值
    while(K--)
    {
         //用筛法把非素数都赋值成0.
         int t,num1=0,num2=0;
         scanf("%d %d",&a,&b);
         for(i=2; i<=a; i++)//对数组进行初始化
        {
            c[i] = i;
        }        
        for(i=2; i<=sqrt(a); i++)//进行筛选
        {
            
            for(j=i+1; j<=a; j++)
            {
                if(c[i]!=0 && c[j]!=0 && c[j]%c[i]==0)
                {
                    c[j]=0;
                }
            }
        }

        for(i=2; i<=a; i++)
        {
            if(c[i]!=0)
            {
                num1++;
            }
        }
        
         for(i=2; i<=b; i++)//对数组进行初始化
        {
            c[i] = i;
        }        
        for(i=2; i<=sqrt(b); i++)//进行筛选
        {
            
            for(j=i+1; j<=b; j++)
            {
                if(c[i]!=0 && c[j]!=0 && c[j]%c[i]==0)
                {
                    c[j]=0;
                }
            }
        }

        for(i=2; i<=b; i++)
        {
            if(c[i]!=0)
            {
                num2++;
            }
        }
        if(num1>num2)
        {
           t=num1;
           num1=num2;
           num2=t;   
        }
        printf("%d\n",num2-num1+1);
    }
    return 0;
}


第二种求法:
#include <stdio.h>
#define  N 1000001
int prime[N];
int main()
{
        int K,i,c;
        scanf("%d",&K);
            for(i=2;i<N;i++)  //筛法求素数
        {
            prime[i]=1;   
        }
        prime[0]=prime[1]=0;
        for(i=2;i<=1000;i++)
        {
            if(prime[i])
            {
                for(c=i*i;c<=N;c+=i)
                {
                    prime[c]=0;   
                }
            }
        }
        while(K--)
        {
            int t,a,b,num=0;
            scanf("%d %d",&a,&b); //输入a b的值,如果a>b则将a与b的值交换
            if(a>b)
            {
                t=a;
                a=b;
                b=t;
            }
               
   
        
        for(i=a;i<=b;i++) //ab之间有多少个素数
        {
            if(prime[i]==1)
            {
                num++;
            }   
        }
        printf("%d\n",num);
    }
    return 0;            
}


测试没问题了,不过我在网站提交还是显示time limit exceed 没有ac还是要继续改
收到的鲜花
  • 九转星河2016-10-31 12:51 送鲜花  5朵   附言:我很赞同
2016-10-30 23:44
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 12楼 Orcaina
第二种思路做法很优,筛数法和我接触传统的穷举法不同,可以大大减少运算量。我自己也尝试做了一个,但我用的穷举法运算量很大,没有你的筛数法优。
我的程序代码如下
程序代码:
#include<stdio.h>
#include<math.h>
int main()
{
    int num,k;
    scanf("%d",&k);//案例个数
    while (k--)
    {
        int i,j,t,a,b;
        scanf("%d%d",&a,&b);//ab为所求区间
        if (a>b)
        {
            t=a;
            a=b;
            b=t;
        }
        for (num=0,i=a;i<b;i++)
        {
            for (t=1,j=2;j<=sqrt(i);j++)
                if (i%j==0)t=0;
            if (t==1&&i!=1)
                num++;
        }
        printf("%d\n",num);
    }
    return 0;/*该方法没有用数组处理,用穷举法,没有标记该数是否是素数,省空间,但运算量大
             适用于的取值范围较小的区间*/
}

我没有用数组处理,直接把素数的值累加。这样可以节省4000004个字节(相当于3MB)的空间,但如果输入区间范围很大,则运算量很大很大,甚至超出了编译器的允许运算范围(我用vc版测试的,我的穷举法不能从1算到1000001),但是当计算区间范围较小的便有空间优势。你可以比较一下两种做法,它们的适用范围不同,但如果不受空间限制,还是题主的做法较优。

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-10-31 12:47
快速回复:求素数的个数,出现未输入就退出程序的问题,求指点。谢谢~
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.073370 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved