全TLE求调

hanzhenhong @ 2025-01-11 15:12:17

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define ll long long
ll n,q;
ll a[1000010],cnt;
map<ll,bool> ma;
void primes(ll n)
{
    for(int i=2;i<=n;i++)
    {
        if(!ma[i])
        {
            a[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(i*a[j]>=n)
            {
                break;
            }
            ma[i*a[j]]=true;
            if(i%a[j]==0)
            {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    primes(n);
    while(q--)
    {
        ll x;
        cin>>x;
        cout<<a[x]<<endl;
    }
    return 0;
}

by pjh0625 @ 2025-01-11 15:19:40

@hanzhenhong

#include <bits/stdc++.h>
#define rep(i, l, r)  for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'
const int M = 1e7 + 7;
const int N = 1e8 + 7;
int primes[M],cnt=0;
bool st[N];
void getprime(int n)
{
  for(int i=2;i<=n;i++)
  {
    if(!st[i])
    {
         primes[cnt++]=i;
    }
    for(int j=0;primes[j]<=n/i;j++)
    {
      st[primes[j]*i]=1;
      if(i%primes[j]==0)break;
    }
  }

}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,t;
    cin>>n>>t;
    getprime(n);
    while(t--)
    {
        int m;
        cin>>m;
        cout<<primes[m-1]<<endl;
    }
    return 0;
}

by hanzhenhong @ 2025-01-11 15:22:02

@pjh0625谢大佬%%%