ARTS 第 拾伍 期

Algorithm

Problem: 100377. 判断是否可以赢得数字游戏

思路

本质上要找出 区间内所有质数的平方，2^2 、3^2、5^2

解题过程

使用埃氏素数筛选法：

要得到自然数n以内的全部素数，必须把不大于 的所有素数的倍数剔除，剩下的就是素数。
给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

复杂度

• 时间复杂度: O(NlnlnN)
• 空间复杂度：O(N)

Code

class Solution {
public:
    #define MAX (int)1e5 + 10

    int nonSpecialCount(int l, int r) 
    {
        int status[MAX] = {0};
        int cnt = 0;
        int sq_r = sqrt(r);

        for(int i = 2; i * i <= r; i ++) {
            if(status[i])
                continue;

            if(i * i >= l) //素数筛出
                cnt++;

            for(int j = i * i; j <= sq_r;j += i) //去除倍数
                status[j] = 1;
        }

        return r - l + 1 - cnt;
    }
};

Review

graphrag 微软开源的基于 graph 的 rag 系统
https://github.com/microsoft/graphrag

Tip

bazel 实现交叉编译，可以使用 platforms：

https://bazel.build/extending/platforms?hl=zh-cn
https://bazel.build/extending/platforms?hl=zh-cn

Share

达利欧《原则》中有一句：

把复杂的系统设想为机器，发现其内部的因果关系，把处理这些因果关系的原则写下来，将其输入计算机，从而让计算机为我“决策”。

牛人的决策系统不是不会犯错，而是通过借助外力来少犯错，让决策系统“自动驾驶”化。

打赏作者