线性筛素数

【模板】线性筛素数 - 洛谷 / 【深基7.例2】质数筛 - 洛谷 / #include <iostream> #include <bitset> typedef long long ll; const int sz=1e8+10; namespace sscio { inline ll pull() { ll sign = 1LL,res = 0LL; char ch = getchar(); for (;!isdigit(ch);ch=getchar()) { if (ch == '-') { sign *= -1LL; } } for (;isdigit(ch);ch = getchar()) { res = (res << 3) + (res << 1) - '0' + ch; // *10 } return sign * res; } } using std::bitset; bitset<sz> primeTable; int primes[sz],prpp=0; void fetchPrimes(const int &ed) { //线性筛 形参为边界 primeTable.reset(); primeTable.set(0); primeTable.set(1); for(register int cx=2;cx<ed;cx++) { if(!primeTable[cx]) { primes[prpp++]=cx; } for (register int cy=0;cy<prpp&&cx*primes[cy]<ed;cy++) { //用质数来筛质数 primeTable.set(cx*primes[cy]); if (cx%primes[cy]==0) { break; } } } } void solve() { fetchPrimes(sz-6); int n=sscio::pull(); //n为查询范围,因为已经筛了超出题目范围素数了,所以无需处理 int p=sscio::pull(); //查询的个数 while(p--) { int k=sscio::pull(); //表示查询第 k 小的素数 printf("%d\n", primes[k-1]); //因为我们下标从零开始 所以是k - 1 } } signed main() { solve(); return 0 ^ 0; } #include <iostream> #include <bitset> typedef long long ll; const int sz=1e5+10; namespace sscio { inline ll pull() { ll sign = 1LL,res = 0LL; char ch = getchar(); for (;!isdigit(ch);ch=getchar()) { if (ch == '-') { sign *= -1LL; } } for (;isdigit(ch);ch = getchar()) { res = (res << 3) + (res << 1) - '0' + ch; // *10 } return sign * res; } } using std::bitset; bitset<sz> primeTable; int primes[sz],prpp=0; void fetchPrimes(const int &ed) { //线性筛 形参为边界 primeTable.reset(); primeTable.set(0); primeTable.set(1); for(register int cx=2;cx<ed;cx++) { if(!primeTable[cx]) { primes[prpp++]=cx; } for (register int cy=0;cy<prpp&&cx*primes[cy]<ed;cy++) { //用质数来筛质数 primeTable.set(cx*primes[cy]); if (cx%primes[cy]==0) { break; } } } } void solve() { fetchPrimes(sz-6); // int n=sscio::pull(); //n为查询范围,因为已经筛了超出题目范围素数了,所以无需处理 int p=sscio::pull(); //查询的个数 int cnt = 0; //空格数量 while(p--) { int k=sscio::pull(); if (!primeTable[k]) { if (cnt==0) { cnt++; } else { putchar(' '); } printf("%d", k); } } } signed main() { solve(); return 0 ^ 0; }