素数

// 质数判断法一 : 试除法

bool isPrime(int n){
	if(n<2) return 0;
	for(int i=2;i*i<=n;i++){
		if(n%i==0) return 0;
	}
	return 1;
}

最大公约数

int gcd(int a, int b){
	if(a%b==0) return b;
	return gcd(b, a%b);
}

#include <iostream>

using namespace std;

// 埃氏质数筛  1e7
// 所有质数的倍数都是合数（1倍除外）
const int MAX = 1e7 + 5;
// 标记合数
int pri[MAX]; // pri[i] = 0，说明i是质数

// 标记过程，搭配代码自己理解一下
//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
//0 0 0 0 1 0 1 0 1 1  1  0  1  0  1  1  1  0  1  0  1

int main() {
    int n;
    cin>>n;
    // 1不是质数，标记为 1
    pri[1] = 1; 
    // 从2一直遍历到n
    for(int i=2;i<=n;i++){
        // 判断是不是质数
        if(pri[i] == 0){
            // 只标记当前质数i的倍数（从两倍开始）
            for(int j=i*2;j<=n;j+=i){
                pri[j] = 1; // 是合数，标记1
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(pri[i] == 0) cout<<i<<" ";
    }
    return 0;
}

/*
  题目：洛谷P3383
*/
#include <iostream>

using namespace std;

// 欧拉筛（线性筛）  1e8
// 原理：所有质数的倍数都是合数（1倍除外）
// 优化：相比埃氏筛，欧拉筛减少了大量的重复计算，从而效率更高

const int MAX = 1e8 + 5;
// 标记合数
int pri[MAX]; // pri[i] = 0，说明i是质数
int p[MAX];  // 存储质数
int cnt = 0;

// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
// 0 0 0 0 1 0 1 0 1 1  1  0  1  0  1  1  1  0  1  0  1
// 2 3 5 7 11
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	// 正常从2开始找质数，一直找到n
	for(int i=2;i<=n;i++){
		// 如果是质数，把质数i放到p数组里面
		if(pri[i] == 0) p[++cnt] = i; 
		// 遍历每一个质数，去标记每个质数的倍数
		// 注意结束条件，p[i]*i不能超过n (数组不能越界) 
		for(int j=1;j<=cnt && p[j]*i<=n;j++){
			// 标记合数
			pri[ p[j]*i ] = 1;
			// 如果当前的i能被质数整除就结束循环
			if(i%p[j] == 0) break;
		}
	}
	// 获取题目的每轮查询
//	while(m--){
//		int t;
//		scanf("%d",&t);
//		printf("%d\n", p[t]);
//	}
	return 0;
}