蒟蒻的疑惑
查看原帖
蒟蒻的疑惑
768951
_Chronostatis_楼主2023/8/23 21:54

为什么这一题数组 10510^5 RE #3,而开到 10610^6 就过了?

AC CODE:

#include<iostream>
#include<iomanip>

using namespace std;

const int MAXN = 1e6 + 10;

int n,m,ans,tot,prime[MAXN],v[MAXN];

void Sieve(int n){
  for (int i = 2; i <= n; i++){
    if (!v[i]){
      prime[++tot] = i;
    }
    for (int j = 1; j <= tot && i * prime[j] <= n; j++){
      v[i * prime[j]] = 1;
      if (i % prime[j] == 0){
        break;
      }
    }
  }
}

int main(){
  cin >> n >> m;
  Sieve(max(n,m));
  for (int i = 1; i <= tot; i++){
    if (prime[i] >= min(n,m)){
      ans++;
    }
  }
  cout << ans;
  return 0;
}
2023/8/23 21:54
加载中...