m2y_miku
m2y_miku
采纳率0%
2018-12-21 15:55 阅读 2.2k

两个数,求两个数之间素数的个数,数据非常大。

5

题目描述
给你两个数,求两个数之间素数的个数。

输入:

输入有两个数,一个a,一个b,求a到b之间素数的个数
其中1<=a<=b<=1e12
其中b-a<=1e7

输出:

一个数,表示a-b之间素数的个数。

样例输入:

1 10

样例输出:

4

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

3条回答 默认 最新

  • wuerlongxin wuerlongxin 2018-12-21 13:12
    #include <stdio.h>
    #include<math.h>
    
    
    bool isPrime(int num)
    {
        int i = 2;
        if(num <= 1)
        {
            return false;
        }
    
        int sqrNum = sqrt(num);
    
        for(i = 2; i <= sqrNum; i++)
        {
            if(num % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    
    int getPrimeCount(int a, int b)
    {
        int sum = 0;
        if(a > b)
        {
            return sum;
        }
    
        for(; a <= b; a++)
        {
            if(isPrime(a))
            {
                sum++;
            }
        }
        return sum;
    }
    
    int main()
    {
        int a, b;
        printf("input two num:\n");
        scanf("%d %d", &a, &b);
        printf("sum is %d\n", getPrimeCount(a, b));
    }
    

    两个函数,分别是判断是否为素数,和获取两个数之间素数的个数。为了快速得出是否为素数,这里只判断小于该数的开方的数能否被除尽。

    点赞 1 评论 复制链接分享
  • u013434984 潭溪Zerg 2018-12-21 09:03

    素数生成的规律至今数学家都还没搞明白吧,估计没啥好的简化方法
    遍历筛选吧

    点赞 评论 复制链接分享
  • qq_43700916 450886768 2019-03-19 20:23
    #include <bits/stdc++.h>
    using namespace std;
    
    #define max1 1000007
    #define max2 10000007
    bool prime[max1], big_prime[max2];//分别是1e6内素数和a-b之间素数
    
    void init()//求出1e6内所以素数
    {
        memset(prime, 1, sizeof(prime));
        memset(big_prime, 1, sizeof(big_prime));//1为素数,0为非素数
        prime[0] = prime[1] = 0;//特殊情况,0和1不是素数
        for (int i = 2; i*i<max1; i++)
        {
            if (prime[i])
            {
                for (int j = i*i; j<max1; j += i)
                {
                    prime[j] = 0;
                }
            }
        }
    }
    
    int main()
    {
        init();
        long long head, tail;
        cin >> head >> tail;
        for (int i = 2; i<max1; i++)
        {
            if (prime[i])
            {
                for (long long j = head / i; j*i <= tail; j++)
                {
                    if (j*i >= head&&j>1)big_prime[j*i - head] = 0;
                }
            }
        }
        if (head == 1)big_prime[0] = 0;//特殊情况
        int ans = 0;
        for (int i = 0; i <= tail - head; i++)
            if (big_prime[i])
                ans++;
    
        cout << ans;
        return 0;
    }
    

    两次素数筛求解

    点赞 评论 复制链接分享

相关推荐