给我一段线性筛的代码

当然可以。下面是一个简单的Python版本的线性筛（克拉斯廷宁筛）代码示例，用于找出小于给定上限的所有质数：

def linear_sieve(n):
    primes = [True] * (n + 1)
    p = 2
    while p * p <= n:
        # 如果p是质数
        if primes[p]:
            # 将p的倍数标记为非质数
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1

    # 输出质数列表
    prime_list = [p for p in range(2, n + 1) if primes[p]]
    return prime_list

# 示例：获取小于50的所有质数
print(linear_sieve(50))

在这个代码里，我们首先创建一个布尔数组`primes`，假设所有数都是质数。然后从2开始，找到每个质数并将其倍数标记为合数。最后返回所有标记为质数的位置对应的实际数值作为结果。

相关问题

帮我写一段C++基于线性筛的自然数幂求和算法，规模为1e6

当然可以，下面是基于线性筛的自然数幂求和算法，规模为1e6：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAXN 1000000

int prime[MAXN + 1];
int phi[MAXN + 1];
long long ans[MAXN + 1];

void get_prime() {
    memset(prime, 0, sizeof(prime));
    memset(phi, 0, sizeof(phi));
    memset(ans, 0, sizeof(ans));
    phi[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (prime[i] == 0) {
            prime[++prime[0]] = i;
            phi[i] = i - 1;
            ans[i] = i - 1;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= MAXN; j++) {
            prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                ans[i * prime[j]] = ans[i] + phi[i * prime[j]];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
                ans[i * prime[j]] = ans[i] + ans[prime[j]];
            }
        }
    }
}

int main() {
    get_prime();
    long long sum = 0;
    for (int i = 1; i <= MAXN; i++) {
        sum += ans[i];
    }
    printf("%lld\n", sum);
    return 0;
}

希望这份代码能够帮助到你。

线性筛法求素数java版

### 回答1：
线性筛法是一种常用的求素数的方法，它的思想简单且高效。下面是使用Java语言实现线性筛法求素数的代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class LinearSieve {
    public static List<Integer> getPrimes(int n) {
        boolean[] isComposite = new boolean[n + 1];
        List<Integer> primes = new ArrayList<>();
 
        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primes.add(i);
            }
 
            for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
                isComposite[i * primes.get(j)] = true;
 
                if (i % primes.get(j) == 0) {
                    break;
                }
            }
        }
 
        return primes;
    }
 
    public static void main(String[] args) {
        int n = 100;
        List<Integer> primes = getPrimes(n);
        
        System.out.println("从 2 到 " + n + " 的素数为：");
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}

以上代码中，我们使用了一个布尔数组`isComposite`来标记是否为合数。初始时，将所有数都标记为非合数。然后从2开始，遍历到n，如果某个数i是合数，则跳过；如果是素数，则将其加入到素数列表中，并标记它的倍数为合数。遍历结束后，我们得到了从2到n的所有素数。

在main函数中，我们设置n为100，调用`getPrimes`函数获取从2到100的素数，并打印出来。

运行结果为：从 2 到 100 的素数为：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97。

### 回答2：
线性筛法是一种高效地筛选出一定范围内的素数的算法。下面是用Java实现线性筛法求素数的代码：

import java.util.*;

public class LinearSieve {
    public static List<Integer> sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true); // 将所有数初始化为素数

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i]) {
                primes.add(i); // 将素数加入结果列表
            }

            for (int j = 0; j < primes.size() && i * primes.get(j) <= n; ++j) {
                isPrime[i * primes.get(j)] = false; // 将当前素数倍数标记为非素数
                if (i % primes.get(j) == 0) {
                    break; // 若当前数为素数倍数，跳出内层循环
                }
            }
        }

        return primes;
    }

    public static void main(String[] args) {
        int n = 100; // 范围上限
        List<Integer> primes = sieve(n);

        System.out.println("范围[2, " + n + "]内的素数有：");
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}

通过线性筛法，我们首先将所有数初始化为素数，然后从2开始，将每个素数的倍数标记为非素数，直到筛选结束。最后，将筛选出的素数存入结果列表中。在上述代码中，我们以100为例，调用`sieve`方法求解范围内的素数，并输出结果。

当我们运行上述代码时，将会得到范围[2, 100]内的素数列表：

范围[2, 100]内的素数有：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

以上就是使用Java实现线性筛法求素数的代码及结果。

### 回答3：
线性筛法是一种用于求解素数的算法，可以高效地找出某一个范围内的所有素数。下面是使用Java语言实现线性筛法求素数的代码：

import java.util.ArrayList;
import java.util.List;

public class PrimeNumbers {
    public static List<Integer> getPrimeNumbers(int n) {
        List<Integer> primeNumbers = new ArrayList<>();
        boolean[] isComposite = new boolean[n + 1];

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primeNumbers.add(i);
            }

            for (int j = 0; j < primeNumbers.size() && i * primeNumbers.get(j) <= n; j++) {
                isComposite[i * primeNumbers.get(j)] = true;

                if (i % primeNumbers.get(j) == 0) {
                    break;
                }
            }
        }

        return primeNumbers;
    }

    public static void main(String[] args) {
        int n = 100;
        List<Integer> primeNumbers = getPrimeNumbers(n);
        
        System.out.println("在[2, " + n + "]范围内的素数有：");
        for (int number : primeNumbers) {
            System.out.println(number);
        }
    }
}

这段代码使用了一个布尔数组isComposite来记录某个数是否为合数（非素数），初始时假设所有数都是质数，然后从2开始遍历到n，如果某个数i没有被标记为合数，就将其添加到素数列表中，并将i与已有的质数依次相乘，将其标记为合数。

运行以上代码，可以求解出2到100之间的所有素数。输出结果如下：

在[2, 100]范围内的素数有：
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

通过线性筛法，我们可以高效地找到某个范围内的素数，而不需要遍历所有的数进行判断。