• 204.计数质数 | 372.超级次方


    204.计数质数

    给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。

    示例 1:

    输入:n = 10
    输出:4
    解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
    示例 2:

    输入:n = 0
    输出:0

    思路:

    如何高效寻找素数 :: labuladong的算法小抄 (gitee.io)

    如下图,找到小于120所有素数

    首先从 2 开始, 2 是一个素数,那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。

    然后发现 3 也是素数,那么 3 × 3 = 6, 3 × 4 = 12, 3 × 5 = 15… 也都不可能是素数了。

    5 也是素数,那么5 x 5 = 25,5 x 6 = 30,5 x 7 = 35…也都不可能是素数。

    以此类推,剩下的数字就是素数。

     

    1. class Solution {
    2. public:
    3. int countPrimes(int n) {
    4. vector<bool> isPrime(n,true);
    5. /*
    6. //存在重复计算,如i=2时会遍历4,6,8,10,12等位置,而i=3时,会遍历6,9,12等位置
    7. //6被重复遍历,所以j=i*i开始,i=3时,从3X3=9开始遍历,避免重复计算
    8. for(int i=2;i
    9. {
    10. if(isPrime[i])
    11. {
    12. for(int j=i*2;j
    13. {
    14. isPrime[j]=false;
    15. }
    16. }
    17. }
    18. */
    19. for(int i=2;i*i//因为从j=iXi开始,所以iXi要小于n
    20. {
    21. if(isPrime[i])
    22. {
    23. for(int j=i*i;j
    24. {
    25. isPrime[j]=false;
    26. }
    27. }
    28. }
    29. int count=0;
    30. for(int i=2;i
    31. {
    32. if(isPrime[i])
    33. count++;
    34. }
    35. return count;
    36. }
    37. };

    372.超级次方

    你的任务是计算 ab 对 1337 取模,a 是一个正整数,b 是一个非常大的正整数且会以数组形式给出。

    示例 1:

    输入:a = 2, b = [3]
    输出:8
    示例 2:

    输入:a = 2, b = [1,0]
    输出:1024
    示例 3:

    输入:a = 1, b = [4,3,3,8,5,2]
    输出:1
    示例 4:

    输入:a = 2147483647, b = [2,0,0]
    输出:1198

    思路:

    如何高效进行模幂运算 :: labuladong的算法小抄 (gitee.io) 

    如何处理数组b:

     

     如何处理%运算:

    (a * b) % k = (a % k)(b % k) % k

    如何高效求幂:

    1. class Solution {
    2. public:
    3. int base=1337;
    4. //返回a的k次方对1337取模以后的结果
    5. int myPow(int a,int k)
    6. {
    7. if(k==0)//base case
    8. {
    9. return 1;
    10. }
    11. a%=base;
    12. if(k%2==1)
    13. {
    14. return (a*myPow(a,k-1))%base;
    15. }
    16. else
    17. {
    18. int tmp=myPow(a,k/2);
    19. return (tmp*tmp)%base;
    20. }
    21. }
    22. //返回a的(b[n]b[n-1]...b[0])次方对1337取模以后的结果
    23. int superPow(int a, vector<int>& b) {
    24. if(b.empty())//base case
    25. {
    26. return 1;
    27. }
    28. int last=b.back();
    29. b.pop_back();
    30. return (myPow(a,last)*myPow(superPow(a,b),10))%base;
    31. }
    32. };
  • 相关阅读:
    【LCR 170. 交易逆序对的总数】
    c语言系统编程之多进程
    C++ 语言学习 day10 复习(1)
    eMMC编程基础 - (一)eMMC相关术语和概念
    脏牛提权 liunx
    【软件测试】常用ADB命令
    深入解析Rivest Cipher 4:理论与实践
    restful请求风格的增删改查-----查询and添加
    Pytorch学习——梯度下降和反向传播 03 未完
    JZ4 二维数组中的查找
  • 原文地址:https://blog.csdn.net/weixin_50437588/article/details/126772714