EDITORIAL
PROBLEM NAME : Prikshit & Prime Pairs
DIFFICULTY : Easy
PREREQUISITES : Sieve
PROBLEM : A P-prime is defined as an integer which has exactly 3 prime-divisors excluding the number itself and 1.
Prikshit is obsessed with P-primes. He calls a pair of two integers good, if the sum of the elements of the pair add up to a P-prime number. He is given an array
A which has N integers. He wants to find the number of good pairs in the array. As he is busy fixing his laptop, he needs your help to find the number of good pairs.
Formally, you are given N integers: A_1,A_2,...,A_N. You need to count the number of pairs of indices (i,j) such that 1≤i<j≤N and A_i+A_j is P-prime.
TASK : Count the number of pairs of indices (i,j) such that 1≤i<j≤N and A_i+A_j is P-prime.
CONSTRAINTS :
1 ≤ T≤ 10
2 ≤ N ≤ 10^3
1 ≤ A_i ≤ 10^6
SAMPLE INPUT (1) :
1
5
28 2 1 2 3
SAMPLE OUTPUT (1) :
2
EXPLANATION :
To approach this problem you must know how to implement classical ‘sieve’.
Refer to this link for more information : Sieve of Eratosthenes - Algorithms for Competitive Programming
Modify your classical sieve such that it stores the count of prime numbers that divides a particular number.
Create an array is_prime (initialized with 1 for each index) to keep track of the number of prime divisors for a given number.
Iterate through the array, increasing the current index’s count whenever a new prime number can divide that particular number.
Check for every pair if the sum has a count of ‘4’ (As we are excluding the number itself) in our is_prime array and print the count.
SOLUTION:
#include <bits/stdc++.h>
using namespace std;
int is_prime[10000001];
void sieve(){
// marking all the numbers true
for(int i=2; i < 10000001; i++){
is_prime[i] = 1;
}
is_prime[0] = is_prime[1] = 0;
// selecting a true value and marking all its multiples
for(int i=2; i*i <= 10000000; i++ ){ // We do this until i = sqrt(n)
if(is_prime[i]==1){
for(int j = i+i; j<10000001; j+=i){
is_prime[j]++;
}
}
}
// Now the array positions, whose value is true , are prime,
}
void solve(){
int n; cin >> n;
vector<int> a(n,0);
for(int &x : a) cin >> x;
int ct = 0;
for(int j=1;j<n;j++){
for(int i=j-1;i>=0;i--){
if(is_prime[a[i]+a[j]]-1 == 3) ct++;
}
}
cout << ct << endl;
}
int32_t main(){
sieve();
int t;
cin >> t;
int counter = 1;
while(t--){
// cout << "Case #" << counter <<": " ;
solve();
counter++;
}
return 0;
}
OPTIMAL COMPLEXITY :
Time - O(N2+N*log(logN))
Space - O(N)