Please provide the approach of the following ,I have tried but i didn't came up with a good approach
You are given an array A of length N and an integer K. It is given that a number m is called special if gcd(m,Aj) = 1 for all 0<=j<N
Let R be an array containing all special number in the range [ 1 , K ] inclusive in sorted order . Your task is to return R.
Note : A follows 0-based indexing.
Input Format The first line contains an integer N , denoting the number of elements in A. The next line contains an integer K , denoting the given integer. Each line i of the N subsequent lines (where 0<=i<N) contains an integer describing A[i].
Constraints 1<=N<=10^5 1<=K<=10^5 1<=A[i]<=10^5
Sample Input Sample Output 3 1 5 5 1 2 3
4 1 5 2 3 4 3 5 7
4 1 1 1 1 1 1
For all x in [1, K], for all prime p such that p divides x if p doesn't divide any A[i] (0 <= i < N) then include x in our ans.
Composite numbers can also be in the answer
read again, i am including x in ans, not prime p
TLE? Are you making any optimization on checking whether p divides any ai ?
its pretty straightforward, just keep a boolean array have[x] (does any number in array has x in its prime factorization). To compute have[x], just iterate on all prime factors of numbers in array. You can do it with sieve or using the naive sqrt algorithm
Use the fact that you can find divisors of a number ai in sqrt(ai). Maintain a set which initially contains all numbers from 1 to k. For each ai, for each divisor if the divisor is in set then remove it. The set contains all your numbers.
Complexity: O((N*sqrt(Ai)+K)*logK)
this is wrong, since you only remove divisors of Ai, numbers other than divisors can also have gcd > 1
Seems right to me. Can you give an example?
if A={6} and K=4
Then set will originally have {1,2,3,4}.
We will remove {1,2,3,6} from the set and then the set will have {4} which is not a special number as gcd(4,6)==2 which is not equal to 2.
okok. Got it. What will your approach be though. I can only come up with the bruteforce approach which includes looping through all the values of X and checking there gcd with each element
Don' know if it would work or not.
Do fast prime factorization of number in log(A[i]) complexity.
Use harmonic series sum property to mark all multiples of these primes and then whichever numbers are unmarked are returned.