(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个回答

phenix2009
白色一大坨 啧啧,一点长进都没有,就会复制粘贴
2 个月之前 回复
qq_45359965
qq_45359965 这里面的两种方法都不行呀,第一种是从2遍历到n-1,时间超限,第二种用到了sqrt函数,但参数精度不够呀
2 个月之前 回复

这是我目前了解到的,速度最快的素数判断方法,六倍法:

int isPrime(int x)
{
    int i;
    if (x <= 1)
        return 0;
    if (x == 2 || x == 3 || x == 5)
        return 1;
    if (x % 2 == 0 || x % 3 == 0)   /*判断是否为2,3的倍数*/
        return 0;
    for (i = 6; i <= sqrt(double(x)); i += 6){
        if (x % (i - 1) == 0 || x % (i + 1) == 0)
            return 0;
    }
    return 1;
}
#include <stdio.h>
#include <math.h>

int primes[1000000];
int np;

int isp(int n)
{
    if (n <= primes[np - 1])
    {
        int i = np - 1;
        while (i >= 0 && primes[i] >= n)
            if (n == primes[i--]) return 1;
        return 0;
    }
    int x = primes[np - 1] + 2;
    while (primes[np - 1] < n)
    {
        int ip = 1;
        for (int i = 0; primes[i] <= (int)sqrt((double)x); i++)
        {
            if (x % primes[i] == 0)
            {
                ip = 0;
                break;
            }
        }
        if (ip) primes[np++] = x;
        x += 2;
    }
    return isp(n);
}

int main()
{
    primes[0] = 2;
    primes[1] = 3;
    np = 2;
    int n;
    scanf("%d", &n);
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        int m;
        scanf("%d", &m);
        if (isp(m)) cnt++;
    }
    printf("%d", cnt);
    return 0;
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

2
一个素数的问题,但是求的是素数的个数,怎么利用C语言的办法解决的
0
伪素数的判断问题,基于进制的转换,采用C语言实现的办法怎么做到
1
为什么用素数表来求素数反而比暴力求解还要来得慢?
1
先判断是否是质数然后统计个数的问题怎么利用C语言程序写的办法来实现
3
请问C语言中多余的空行是怎么回事呀?是编译器的问题吗?
0
素数的判断,多个数字连续的输入后的判断怎么利用C语言的办法来编写的
0
判断一个数字是否是伪素数的程序的编写,怎么使用的C语言的程序编写的办法来设计一个程序去实现的
1
判断多个数据是否是两素数相乘
0
反素数,用C语言来计算怎么计算
1
一道用c语言判断素数的题
2
c语言寻找素数数据溢出问题
1
素数如何用C语言来判定
2
判断一个数是不是素数
1
C语言 关于筛选法求素数的问题 求大佬帮助!
2
质数组成的整数? C语言
1
C语言计算1000以内的质数的和,并且输出出来,代码
1
C语言 判断输入数字是否为素数 输入1到17判断都是正确的(只试到17) 但是输入9判断结果是“9是素数” 而且就9这一个数字这样 求解??
1
读出20个数判断是否为素数
1
编写函数,判断该数组中哪些是素数,并统计素数的个数,在主函数中输出素数的个数和这些素数,函数原型不能变,怎么我一直输出不来,求大神指教!?
1
Java语言程序编写,计算1000以内所有质数的和,怎么计算