atCoder 計算量の見積もりがあってるか教えてほしいです。

Question

https://atcoder.jp/contests/abc215/tasks/abc215_d
この問題を解いていたのですが、思いついた解法が計算量的にNGだと思っていたらそれで正解だったみたいです。

一番下のコードが模範解答なのですが、自分的には制限時間以内に終わらないと思っていたため、自分の見積もりのどこが間違っているのか教えてほしいです。

以下自分の計算量見積もり

1. 実行制限時間が2秒のためfor 文ループの回数は、2*10^8程度。簡単に考えて10^8。
2. 以下の処理において部分部分で大体コメントの通りの計算量のため処理全体で大体　O(N) * O(sqrt(N)) + O(N) * O(NlogN)　と見積もる
3. Nの最大値を10^5と考え大体の計算でO(10^5) * O(10^2) + O(10^5) * O(10^5)のため、適当に見積もっても(10^10)のため間に合わない

　
  for(int i=0;i<n;i++){ // O(N)
    int a;
    cin >> a;
    vector<int> v=pfact(a); //pfact関数はO(sqrt(N))で終わる
    for(auto &nx : v){
      if(fl[nx]){
        for(int j=nx;j<SIZE;j+=nx){fl[j]=false;} //このfor ループはO(NlogN)
      }
    }
  }

ソースコード全体

#include<bits/stdc++.h>
#define SIZE 100005

using namespace std;

vector<int> pfact(int x){
  vector<int> res;
  for(int i=2;i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res.push_back(i);
    }
  }
  if(x!=1){res.push_back(x);}
  return res;
}

int main(){
  int n,m;
  cin >> n >> m;
  vector<bool> fl(SIZE,true);
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    vector<int> v=pfact(a);
    for(auto &nx : v){
      if(fl[nx]){
        for(int j=nx;j<SIZE;j+=nx){fl[j]=false;}
      }
    }
  }
  vector<int> res;
  for(int i=1;i<=m;i++){
    if(fl[i]){res.push_back(i);}
  }
  cout << res.size() << '\n';
  for(auto &nx : res){cout << nx << '\n';}
  return 0;
}

Answer 1

for(auto &nx : v){
  if(fl[nx]){
    for(int j=nx;j<SIZE;j+=nx){fl[j]=false;} //***
  }
}

**の見積もりが誤ってます。そのループは、篩にかけていない素因数があった場合だけ実行されるので、全体でせいぜいO(SIZElog(SIZE))の計算量になります。その部分を除いて考えると、ループ内の計算は配列のアクセスと0との比較だけなので、計算量はO(1)です。したがって、上記ループ全体の計算量は、O(logN)となります。