Help needed — TLE even with using sieve to prime factorize

Revision en1, by Hustle_Loyalty_Respect, 2020-11-12 12:04:03

The problem I am solving is E. Coprime (in At coder's Beginners contest)

My submission that gives TLE

https://atcoder.jp/contests/abc177/submissions/18061844

The problem I am facing comes with identifying if the numbers are pairwise coprime.

I did exactly what the editorial said — There should be no prime number that divides 2 numbers in the input array otherwise their gcd won't be 1. So I found out unique numbers that are prime factors for every number in the array and then when I spot that there exists a prime number which is a factorizing 2 numbers I set the ispwc = false (is_pairwise_coprime). But I get TLE

My code:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll cnt;

ll gcd(ll a , ll b) {

if(a < b) {
return gcd(b, a);
}

if(b==0)
return a;

return gcd(b, a % b);
}

vector<bool> is_prime;
vector<ll> siever;

vector<ll> upf(ll n) {

assert(n != 0 && n != 1);

// return unique primes that factorize n

// for n = 100, we return [2, 5]

vector<ll> res(n + 1);
vector<ll> uniqs;

ll curr = n;

do {

if(res[siever[curr]] == 0){
uniqs.push_back(siever[curr]);
}
res[siever[curr]]++;

curr = curr/siever[curr];

if(curr == siever[curr]) {

if(is_prime[siever[curr]] && res[siever[curr]] == 0) {
uniqs.push_back(siever[curr]);
res[siever[curr]]++;
}

break;
}

} while(true);

return uniqs;
}

void sieve(ll n) {

is_prime.assign(n + 1, true);
siever.assign(n + 1, 0);

for(ll i = 0; i < n + 1; ++i) {
siever[i] = i;
}

is_prime = is_prime = false;

for(ll i = 2; i <= sqrt(n); ++i) {

if(is_prime[i]) {

for(ll j = i * i; j <= n; j += i) {
siever[j] = i;
is_prime[j] = false;
}

}
}

}

int main() {

ios::sync_with_stdio(false);
cin.tie(0);

ll n;
cin >> n;

// accumulator for setwise gcd
ll c = 0;

sieve(1000001);

// is pairwise coprime
bool ispwc = true;

for(ll i=0; i<n; ++i) {

ll x;
cin >> x;

c = gcd(c, x);

if(x != 1) {

// for each unique prime factor of x
for(ll _p: upf(x)) {

// cout << _p << " ";

if(cnt[_p] != 0) {
ispwc = false;
}

cnt[_p]++;
}

// cout << "\n";

}

}

// is setwise coprime
bool isswc = c == 1;

if(ispwc) {
cout << "pairwise coprime" << endl;
}
else if(isswc) {
cout << "setwise coprime" << endl;
}
else {
cout << "not coprime" << endl;
}

return 0;
}


#### History

Revisions Rev. Lang. By When Δ Comment
en1 Hustle_Loyalty_Respect 2020-11-12 12:04:03 2727 Initial revision (published)