Hello. During the contest, I made a double loop with this problem and TLE. I don't remember the basic algorithm yet, so I want to be able to use it properly. This problem seems to save a lot of computation using the same principles as the Eratosthenes sieve.
code.py
N = int(input())
A = list(map(int, input().split()))
A.sort() #Sort for eratosthenes sieving
Amax = A[-1]
dp = [1]*(Amax+1) #Make a sieve of Eratosthenes up to the maximum value of A.
ans = 0
for i in range(len(A)-1):
p = A[i]
if dp[p] == 1: #A[i]Is A[j]Check with an Eratosthenes sieve to see if it is a multiple of
for q in range(Amax//p+1):
dp[p*q] = 0 #A[i]Set all multiples of
if A[i] != A[i+1]:
ans += 1 #A[i]Count if does not overlap
if dp[Amax] == 1: #Since the range is over when checking for duplicates, only Amax is judged separately.
ans += 1
print(ans)
dp is in the initial state dp = [1 1 1 1 1 1 1 ...].
For example If A [0] = 3, the dp after one operation is dp = [0 1 1 0 1 1 0 ...].
Recommended Posts