SANTAFAV-Editorial

PROBLEM LINK:

PRACTICE
Editorialist: Shivam Kumar

DIFFICULTY:

MEDIUM

PREREQUISITES:

Number Theory

PROBLEM:

Santa Claus loves to play with numbers since childhood. Santa’s mother has given him an array of numbers and tells him to choose any two number where both has three factors separately. For e.g.: - If the array is [ 5, 6, 25, 4], then factors of 25 are 1, 5, 25, and factors of 4 are 1, 2, 4. So Santa can choose both numbers 25 and 4. Santa asks you to tell him is it possible to choose any two numbers where both the number has three factors separately. Input First line contains n (1 <= n <= 10^4) where n is size of the array.
Second line contains n space separated integers ai (1 <= ai <= 10^12) where ai is the i-th element (1 <= i <= n).
Print “Yes”“Yes” (without quotes) if it is possible to choose two number where both has three factors separately else print “No”“No” (without quotes) in single line.

EXPLANATION:

We have to find only two such numbers that has only three factors separately from the given array.
We know that prime numbers have two factors that is 1 and the number itself. So, the square of prime numbers only have three factors. For eg 9 → 1, 3 and 9, 4 → 1, 2 and 4.
For finding the prime numbers we can use seieve of Eratosthenes. Instead of storing prime numbers , we can store the square of the prime numbers.
Then we can use find operation to check whether two such number exit in array or not. If the count is 2 then we break the loop and print ‘Yes’ in the next line else we print ‘No’
Sieve of Eratosthenes → n*log(logn)
Find Operation → n
Time complexity of the solution: n^2 * log(log(n))

SOLUTION:

#include <bits/stdc++.h>
using namespace std;
#define int             long long int
int32_t main()
{
    ios_base::sync_with_stdio(0); 
     cin.tie(0); 
    cout.tie(0);
    vector<int> v(1000000, 1);
    v[2] = 1;
    vector<int> primes;
    for(int i = 2; i*i < 1000000; ++i) {
        if(v[i] == 1) {
            primes.push_back(i*i);
            for(int j = i*i; j < 1000000; j += i) {
                v[j] = 0;
            }
        }
    }
    
    
    
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int count = 0;
    int flag = 0;
    for(int i = 0; i < n; ++i) {
        if(find(primes.begin(), primes.end(), a[i]) != primes.end()) {
            
            count++;
        }
        if(count == 2) {
            flag = 1;
            break;
        }
    }
    
    if(flag == 1) {
        cout << "Yes" << "\n";
    }
    else {
        cout << "No" << "\n";
    }
    return 0;
    
}