【Atcoder】ABC 170 D を茶コーダーが愚直な方法で解いてみた(C++)

#はじめに
エラトステネスの篩を知らない茶コーダーが、連想配列と約数列挙だけ使用してABC 170 D問題を愚直に解きます。

#問題文(公式サイトより引用)

問題文
長さ $N$ の数列 $A$ が与えられます。
次の性質を満たす整数 $i (1 ≤ i ≤ N)$ の数を答えてください。
　・ $i ≠ j$ である任意の整数 $j (1 ≤ j ≤ N)$ について $A_i$ は $A_j$ で割り切れない
制約
　・入力は全て整数
　・$1 ≤ N ≤ 2×10^5$
　・$1 ≤ A_i ≤ 10^6$
入力
入力は以下の形式で標準入力から与えられる。
　$N$
　$A_1 , A_2 , ⋯ , A_N$
出力
答えを出力せよ。

#方針
各 $i$ に対し、 $A_i$ の約数 $d$ が $A_j$ と一致するかを調べる。

　※計算量オーダーは$O(N×\sqrt{A_i})<O(10^9)$なのでC++ではギリギリ通りました。

#手順

1. サイズが$10^6$の連想配列$B[1000000]$に $A_1$ ~ $A_N$ を格納
2. 出力の初期値を $N$ に設定
3. 各 $i$ に対して以下を実行

　・$A_i$ の約数 $d$ を検索
　・以下の条件を満たす時、出力から $-1$
$,,,,,,\,,\begin{cases}
B[d]>0 & (d≠A_i)\
B[d]>1 & (d=A_i)
　　\end{cases}$
　　※入力例2 のように「Aの要素に同じ数が存在する」ケースを通すために、$(d=A_i)$の条件が必要です。

#コード

ABC_170_D.cpp

#include <math.h>
#include <iostream>
#include <stdio.h>

using namespace std;
typedef long long ll;

int main() {
    ll N;
    cin >> N;
    ll B[1000001];
    for(ll i=0;i<1000001;i++) B[i] = 0;
    ll A[N];
    for(ll i=0;i<N;i++){
        cin >> A[i];
        B[A[i]]++;
    }
    ll out = N;
    for(ll i=0;i<N;i++){
        for(ll j=1;j<=sqrt(A[i]);j++){
            if(A[i]%j == 0){
                if(A[i] == 1){
                    if((B[j] > 1)){
                        out--;
                        break;
                    }
                }else if(B[j] > 0){
                    out--;
                    break;
                }else if(j==1){
                    if(B[A[i]/j] > 1){
                        out--;
                        break;
                    }
                }else{
                    if(B[A[i]/j] > 0){
                        out--;
                        break;
                    }
                }
            }
        }
    }
    cout << out << endl;
    return 0;
}

#最後に
連想配列と約数列挙だけを使用して解くことができました。
ただし、問題条件が変わるとこの方法ではTLEになる可能性が高いです。
エラトステネスの篩を身につける必要がありそうです。