当前位置：首页 > article >正文

洛谷P3383 【模板】线性筛素数

article 2025/1/30 19:01:32

题目链接：P3383 【模板】线性筛素数 - 洛谷 | 计算机科学教育新生态

题目难度：普及一

题目分析：本题是模板题，用到了线性筛法，其中原理是保证范围内的每个合数都被删掉（在 bool 数组里面标记为非素数），而且任一合数只被：“最小质因数 × 最大因数（非自己） = 这个合数”

下面奉上代码部分：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e8 + 10;
int prime[N];
bool vis[N];
int n,q,cnt;

void get_prime(int n)
{
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i]) prime[cnt++] = i;
		for(int j = 0; prime[j] <= n / i; j ++) 
		{
			vis[prime[j] * i] = true;
			if(i % prime[j] == 0) break;
		}
	}
}
int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

int main() {
 
    n = read(),q = read();
    get_prime(n);
    
    while(q--)
    {
    	int k = read();
    	cout<<prime[k - 1]<<'\n';
	}
    return 0;
}

查看全文

http://www.kler.cn/a/525020.html