cccccct_1 2020-12-22 13:53 采纳率: 94.1%
浏览 16
已结题

c语言素数问题,萌新求教

输出1~500000以内的素数,共有41538个,每两个素数之间有一个空格。全部输出后,不要再输出空格或回车换行符。

使用下面的原始算法,大概需要计算7分钟。请改进算法,使计算时间缩短在0.2秒钟以内。耗时比是2100倍。

#include <stdio.h>
int main()
{
    int i,j,cnt=0;
    for(i=2;i<=500000;i++)
    {
        cnt=0;
        for(j=1;j<=i;j++)
        {
            if(i%j==0)cnt++;
        }
        if(cnt==2)printf("%d ",i);
    }
}

改进思路:

1、如果是2、3、5、7的倍数,就不要去判断

2、否则,每个数i只判断到sqr(i)即可

  • 写回答

2条回答 默认 最新

  • qq_25376897 2020-12-22 14:42
    关注
    #include <stdio.h>
    #include <math.h>
    
    int isPrimeNumber(int a);//判断素数
    
    int main() 
    {
        int i,j,k;
        int s = isPrimeNumber(2);
        printf("%d",s);
        for(i=2;i<=500000;i++){
            if(isPrimeNumber(i)){
                printf("%d ",i);
            }
        }
        return 0; 
    }
    
    int isPrimeNumber(int a){
        int s = (int)sqrt(a);
        for(int i=2;i<=s;i++){
            if(a%i==0){
                return 0;
            }
        }
        return 1;
    }
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 5月16日
  • 已采纳回答 5月8日

悬赏问题

  • ¥20 wireshark抓不到vlan
  • ¥20 关于#stm32#的问题:需要指导自动酸碱滴定仪的原理图程序代码及仿真
  • ¥20 设计一款异域新娘的视频相亲软件需要哪些技术支持
  • ¥15 stata安慰剂检验作图但是真实值不出现在图上
  • ¥15 c程序不知道为什么得不到结果
  • ¥40 复杂的限制性的商函数处理
  • ¥15 程序不包含适用于入口点的静态Main方法
  • ¥15 素材场景中光线烘焙后灯光失效
  • ¥15 请教一下各位,为什么我这个没有实现模拟点击
  • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来