CODEWITHSUNDEEP
algorithmmathdata-structures
user9409795
user9409795

Reputation: 15

divisibility algorithm on an array of integers

You are given an array of positive integers A. You need to create a subset of the array A with the maximum number of elements with the property that however we take any two numbers of the subset (we can call it x and y), we have that gcd(x,y) is higher than 1. Print the elements of the subset.

For example, if we have n = 4 and the array is {15, 7, 10, 6}, the output needs to be {15, 10, 6}.

Is there any faster solution than backtracking?

Upvotes: 0

Views: 70

Answers (2)

Prune
Prune

Reputation: 77850

Yes, I think you have a better solution. Transform this to a graph problem: each integer is a node; two nodes i and j have an edge connecting them iff gcd(i, j) > 1.

Now, you need to find the largest fully-connected subgraph, (a.k.a. a clique). A little research will show you how to implement that. It's not efficient, but it's more tractable and reliable.

Upvotes: 2

anatolyg
anatolyg

Reputation: 28278

This is equivalent to the Clique problem. So no, there is no efficient solution for this (unless P = NP).

Upvotes: 0

Related Questions