嘿嘿嘿灬 2020-01-16 11:59 采纳率: 0%
浏览 1145

(C语言)怎样判断大数是否是素数?

输入包含多个测试实例,每个实例包含两行,第一行为整数n,第二行有n个整数(每个整数长度不超过32位,并且每个整数不小于2)。
输出素数的个数。

样例输入:

3

2 3 4

样例输出:

2

这是我写的代码,输入小数据的时候没有问题,数一大就不行了,(因为math.h库里的函数sqrt精度不够,所以又写了一个求平方根函数)。

我听别人说这个题可以用线性筛法写,但我看线性筛法是求一个范围内所有素数的算法呀,跟这题的意思好像不一样,也就没有去用。

这个代码是哪里错了可以改进,还是可以用其他的方法去做,求高人指点!!

#include<stdio.h>
long long int msqrt(long long int n)//求平方根
{
    long long int i=0;
    while(1)
    {
        if(i*i<=n)
            i++;
        else
            return i-1;
    }
}
long long int prime(long long int n)
{
    if(n==0)
        return 0;
    if(n==1)
        return 0;
    if(n==2)
        return 1;
    if(n==4)
        return 0;
    long long int i;
    for(i=2;i<msqrt(n);i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}
int main()
{
    long long int x,i,n;
    while(scanf("%lld",&n)!=EOF)
    {
        i=0;
        while(n--)
        {
            scanf("%lld",&x);
            if(prime(x))
                i++;
        }
        printf("%lld",i);
    }
    return 0;
}
  • 写回答

3条回答 默认 最新

  • dabocaiqq 2020-01-16 12:14
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀