姜肆爷 2021-09-08 00:54 采纳率: 76%
浏览 28
已结题

PAT 乙级 1007 运行超时 该如何改进

输入和输出都没有问题,但当我输入10^5^时显示超时
我想问一下是哪部分的代码导致了运行时间超时呢?
该如何改进呢?

#include <stdio.h>
int main(void){  //超时
    int n;
    int cnt = 0;
    int p1=2, p2;
    int k = 0;

    scanf("%d", &n);
    int a[n];
    
    int i, j;
    for( i=2; i<=n; i++){  //只能从2开始 因为1%2==1 但1不是素数
        int isPrime = 1;
        for( j=2; j<i; j++){
            if(i%j==0){
                isPrime =0;
                break;
            }
        }     
        
        if( isPrime == 1){
            p2 = i;
            if(p2-p1==2){
                cnt++;
            }
            p1 = i;
        }
        
    }
    printf("%d", cnt);

    return 0;
}

展开全部

  • 写回答

2条回答 默认 最新

  • 快乐鹦鹉 2021-09-08 00:59
    关注

    你的需求是什么呢?是求小于指定的整数间有多少个素数吗?
    for( j=2; j<i; j++){ 这个循环效率低了
    改为:
    for( j=2; j*j<=i; j++){

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)
编辑
预览

报告相同问题?

问题事件

  • 系统已结题 9月15日
  • 已采纳回答 9月8日
  • 创建了问题 9月8日

悬赏问题

  • ¥15 pycharm倒入虚拟环境的时候,显示这个,但是我的虚拟环境已经创建了
  • ¥15 FPGA芯片60进制计数器
  • ¥15 前端js怎么实现word的.doc后缀文件在线预览
  • ¥20 macmin m 4连接iPad
  • ¥15 DBIF_REPO_SQL_ERROR
  • ¥15 根据历年月数据,用Stata预测未来六个月汇率
  • ¥15 DevEco studio开发工具 真机联调找不到手机设备
  • ¥15 请教前后端分离的问题
  • ¥15 下载honeyd时报错 configure: error: you need to instal a more recent version of libdnet
  • ¥15 距离软磁铁一定距离的磁感应强度大小怎么求
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部