Pairs with Common Factor
MediumPractice library · +20 XPmathnumber theoryprime factorization
Given an array A of N integers, find the number of pairs (i, j) such that 1 <= i < j <= N and the greatest common divisor (GCD) of A[i] and A[j] is greater than 1. Two numbers share a common factor greater than 1 if and only if they share a common prime factor.
Input
The first line contains an integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer: the total count of pairs (i, j) with i < j and GCD(A[i], A[j]) > 1.
Constraints
1 <= N <= 200000 1 <= A_i <= 1000000
Time limit 2 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 2 4 6 8 10
Output
10
All numbers share a common factor of 2. Total pairs = 5*4/2 = 10.
Example 2
Input
4 2 3 5 7
Output
0
All numbers are prime and distinct, so GCD of any pair is 1. 0 pairs.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 2 4 6 8 10
Example 2 input
4 2 3 5 7