| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2307 人关注过本帖
标题:程序超时了怎么办?题目和我写的代码都在下面了。
只看楼主 加入收藏
踩不扁小强
Rank: 2
等 级:论坛游民
帖 子:46
专家分:39
注 册:2013-4-6
结帖率:91.67%
收藏
已结贴  问题点数:20 回复次数:6 
程序超时了怎么办?题目和我写的代码都在下面了。
/*
素数
时间限制:500MS  内存限制:1000K
Description
数学对于计算机学是很重要的,大一的高数就曾经(或即将)令一批又一批人饮恨。这里就是一个数学问题,当然,它不需要用到高深的高数知识。
给出n(1<=n<=100000),问1到n之间有几个素数。
输入格式
第1行,1个整数T(T<=100000),表示共有T组测试数据
第2---第T+1行,每行1个整数,表示测试数据n
输出格式
对于每个测试数据,输出1行,每行1个数,表示1到n之间的素数个数
输入样例
5
1
2
100
1000
5000
输出样例
0
1
25
168
669
 */
#include <stdio.h>

main()
{
    int n,i,a[100000],j,m,s=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        for(j=2,s=0;j<=a[i];j++)
        {
            for(m=2;m<=j/2;m++)
            {
                if(j%m==0)
                    goto L;   
            }
            s++;
            L:;
        }
        printf("%d\n",s);
    }
}
搜索更多相关主题的帖子: 数学 计算机 include 知识 
2013-06-04 21:29
pauljames
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:千里冰封
威 望:9
帖 子:1555
专家分:10000
注 册:2011-5-8
收藏
得分:7 
判断素数n,只需要1到sqrt(n)为除数

经常不在线不能及时回复短消息,如有c/单片机/运动控制/数据采集等方面的项目难题可加qq1921826084。
2013-06-05 06:22
菜鸟一支
Rank: 6Rank: 6
来 自:何美杭
等 级:侠之大者
威 望:1
帖 子:121
专家分:456
注 册:2012-10-10
收藏
得分:7 
素数判定--朴素方法
对于正数n,用i∈ [2,n]或i∈ [2,n/2]或i∈ [2,√𝒏]依次试除,若n/i不等于0在整个区间成立,则n是素数。

小弟何美杭,所发表的都仅代表个人观点,欢迎批评指正。
2013-06-05 10:38
踩不扁小强
Rank: 2
等 级:论坛游民
帖 子:46
专家分:39
注 册:2013-4-6
收藏
得分:0 
我用了几种方法都是显示超时了,哪位大神帮我优化一下
2013-06-06 14:05
a627910865
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2013-6-8
收藏
得分:0 
楼主是acmer?求题号。。。我有一种思路不知道行不行。。先求出100000以内(因为T<=100000)全部素数。。。之后根据输入值去数就是了。。求的时候不要全部去除。。就直接除小于这个数的素数。。。比如5,那么判断是否是素数的时候,就只要除以2和3。4因为能够被2整除,那么能被4整除的都能被2整除了。。。这样的话就可以剪掉大部分计算。。。时间复杂度应该很小了。。。。。特意申请的一个账号回复的。。看到就回复个吧。
2013-06-08 08:55
浮云之冰雪
Rank: 2
等 级:论坛游民
帖 子:74
专家分:89
注 册:2013-5-11
收藏
得分:0 
#include"stdio.h"
#include"math.h"
main()
{
    int n,i,a[100000],j,m,s=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        for(j=2,s=0;j<=sqrt(a[i]);j++)
        {
            for(m=2;m<=sqrt(j);m++)
            {
                if(j%m==0)
                    goto L;   
            }
            s++;
            L:;
        }
        printf("%d\n",s);
    }
}

潇洒不可少!
2013-06-09 12:47
踩不扁小强
Rank: 2
等 级:论坛游民
帖 子:46
专家分:39
注 册:2013-4-6
收藏
得分:0 
回复 5楼 a627910865
其实这个方法我在网上有看到,自己试了一下,但是还是超时
2013-07-08 23:48
快速回复:程序超时了怎么办?题目和我写的代码都在下面了。
数据加载中...
 
   



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

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