2.编写一个函数，利用线性筛选法输出某个整数n以内的所有素数.Python

在Python中，我们可以编写一个函数来利用线性筛选法（也叫埃拉托斯特尼筛法）找出指定范围内所有的素数。以下是实现的一个简单版本：

def linear_sieve_of_eratosthenes(n):
    # 创建一个布尔列表，初始全部标记为True表示每个数字都是潜在的素数
    primes = [True] * (n+1)
    primes[0], primes[1] = False, False  # 0和1不是素数

    # 遍历从2到sqrt(n)，对每个素数，将它的倍数标记为合数
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False

    # 输出大于1的素数
    for num in range(2, n+1):
        if primes[num]:
            print(num)

# 使用函数
linear_sieve_of_eratosthenes(100)  # 打印100以内的所有素数

这个函数首先创建一个布尔数组`primes`，然后从第一个素数2开始，将它的所有倍数都标记为非素数。接着遍历数组，如果一个数被标记为素数，则打印出来。

相关问题

xtu oj 欧拉函数

### XTU OJ 欧拉函数题目解析

欧拉函数 φ(n) 表示的是小于等于 n 的正整数中与 n 互质的数的数量。对于求解欧拉函数值，通常有两种方法：一种是基于定义直接计算；另一种则是利用其性质通过线性筛法来高效处理。

#### 方法一：直接根据定义求解
如果给定一个具体的数值 n，则可以通过遍历从 1 到 n-1 所有整数 k 并检查 gcd(k, n)=1 来统计满足条件的数目作为 φ(n)[^1]的结果。这种方法适用于较小规模的数据范围内的单次查询场景。

def euler_phi_direct(n):
    count = 0
    for i in range(1, n + 1):
        if gcd(i, n) == 1:
            count += 1
    return count

然而，在面对较大输入或者频繁调用的情况下效率较低，因此更推荐使用第二种方式——线性筛选算法来进行批量预处理并快速获取任意位置处的φ值。

#### 方法二：线性筛法优化版
此方法依赖于素数分解以及积性函数特性，可以实现O(NlogN)复杂度内完成大量数据点上欧拉函数值得预先存储。具体来说就是先找出所有的最小质因子p_i及其对应的倍数m=p_j*p_k...*p_l (其中j≤k≤l...)，再依据公式`phi(m)=(p_1−1)*(p_2−1)*…*(p_r−1)`更新对应下标的数组元素。

const int MAXN = 1e6;
int phi[MAXN], prime[MAXN];
bool is_prime[MAXN];

void sieve(int N){
    memset(is_prime,true,sizeof(bool)*MAXN);
    phi[1]=1;
    int cnt=0;
    for(long long i=2;i<=N;++i){
        if(is_prime[i]){
            prime[cnt++]=i;
            phi[i]=i-1;//if p is a prime number then phi(p)=p-1
        }
        for(int j=0;j<cnt&&prime[j]*i<=N;++j){
            is_prime[prime[j]*i]=false;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}

上述C++代码实现了对不超过指定上限范围内所有自然数欧拉函数值的一次性初始化操作。之后针对任何询问可以直接访问已构建好的表项得到即时响应。