Problem p02642 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
import math

sys.setrecursionlimit(10 ** 6)

def debug(s):
    if True:
        print(s)

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while False:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def filterTrue(a):
    return a

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    table = [False for i in range(A[-1]+1)]
    alreadyDid = set()
    for a in A:
        table[a] = True
    for a in A:
        if a in alreadyDid:
            table[a] = False
            continue
        alreadyDid.add(a)
        i = a*2
        while i < len(table):
            table[i] = False
            i += a
    print(len(list(filter(filterTrue,table))))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math

sys.setrecursionlimit(10 ** 6)

# Made for abc097D
class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = [i for i in range(size)]
        self.ranks = [0 for i in range(size)]

    def ancestor(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.ancestor(self.parents[i])
            return self.parents[i]

    def union(self, i, j):
        ip = self.ancestor(i)
        jp = self.ancestor(j)
        if ip == jp:
            return False
        else:
            if self.ranks[ip] > self.ranks[jp]:
                self.parents[jp] = ip
            else:
                self.parents[ip] = jp
                if self.ranks[ip] == self.ranks[jp]:
                    self.ranks[ip] += 1

    def same(self, i, j):
        return self.ancestor(i) == self.ancestor(j)

    def __str__(self):
        parentDict = { }
        for i in range(self.size):
            a = self.ancestor(i)
            if a not in parentDict:
                parentDict[a] = [i]
            else:
                parentDict[a].append(i)
        result = "===UnionFind description===\nSize:" + str(self.size) + "\nGroupCount:" + str(
            len(parentDict)) + "\n\nGroups:\n"
        for k in parentDict.keys():
            elements = ""
            for elem in parentDict[k]:
                elements += " " + str(elem) + ","
            result += "Group-"+str(k)+"(Count:"+str(len(parentDict[k]))+"):["+elements+"]\n"
        return result

def debug(s):
    if False:
        print(s)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    pst = set(get_sieve_of_eratosthenes(A[-1])) if len(A) > 0 else set()
    # debug(f"Sorted: {A}")
    # debug(f"pst {pst}")
    found = []
    c = 0
    i = 0
    while i < len(A):
        # debug(f"step: A{A[i]}. found:{found}")
        if i < len(A)-1 and A[i] == A[i+1]:
            found.append(A[i])
            ni = i+1
            while A[ni] == A[i]:
                if len(A)-1 == ni:
                    ni = len(A)
                    break
                ni += 1
            # debug(f"i was skipped from {i} to {ni}")
            i = ni
            continue
        else:
            contained = False
            if A[i] not in pst:
                # debug(f"{A[i]} is not a prime")
                for f in found:
                    # debug(f"Dividing {A[i]} with {f}. == {A[i]%f}")
                    if A[i] % f == 0:
                        # debug(f"{A[i]} was divided with {f}")
                        contained = True
                        break
                    if A[i]**2 < f:
                        break
            if not contained:
                # debug(f"{A[i]} is not contained appending")
                c+=1
                found.append(A[i])
            i+=1
    print(c)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math

sys.setrecursionlimit(10 ** 6)

# Made for abc097D
class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = [i for i in range(size)]
        self.ranks = [0 for i in range(size)]

    def ancestor(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.ancestor(self.parents[i])
            return self.parents[i]

    def union(self, i, j):
        ip = self.ancestor(i)
        jp = self.ancestor(j)
        if ip == jp:
            return False
        else:
            if self.ranks[ip] > self.ranks[jp]:
                self.parents[jp] = ip
            else:
                self.parents[ip] = jp
                if self.ranks[ip] == self.ranks[jp]:
                    self.ranks[ip] += 1

    def same(self, i, j):
        return self.ancestor(i) == self.ancestor(j)

    def __str__(self):
        parentDict = { }
        for i in range(self.size):
            a = self.ancestor(i)
            if a not in parentDict:
                parentDict[a] = [i]
            else:
                parentDict[a].append(i)
        result = "===UnionFind description===\nSize:" + str(self.size) + "\nGroupCount:" + str(
            len(parentDict)) + "\n\nGroups:\n"
        for k in parentDict.keys():
            elements = ""
            for elem in parentDict[k]:
                elements += " " + str(elem) + ","
            result += "Group-"+str(k)+"(Count:"+str(len(parentDict[k]))+"):["+elements+"]\n"
        return result

def debug(s):
    if False:
        print(s)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    pst = set(get_sieve_of_eratosthenes(A[-1])) if len(A) > 0 else set()
    # debug(f"Sorted: {A}")
    # debug(f"pst {pst}")
    found = []
    c = 0
    i = 0
    while i < len(A):
        # debug(f"step: A{A[i]}. found:{found}")
        if i < len(A)-1 and A[i] == A[i+1]:
            found.append(A[i])
            ni = i+1
            while A[ni] == A[i]:
                if len(A)-1 == ni:
                    ni = len(A)
                    break
                ni += 1
            # debug(f"i was skipped from {i} to {ni}")
            i = ni
            continue
        else:
            contained = False
            if A[i] not in pst:
                # debug(f"{A[i]} is not a prime")
                for f in found:
                    # debug(f"Dividing {A[i]} with {f}. == {A[i]%f}")
                    if A[i] % f == 0:
                        # debug(f"{A[i]} was divided with {f}")
                        contained = True
                        break
            if not contained:
                # debug(f"{A[i]} is not contained appending")
                c+=1
                found.append(A[i])
            i+=1
    print(c)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math

sys.setrecursionlimit(10 ** 6)

# Made for abc097D
class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = [i for i in range(size)]
        self.ranks = [0 for i in range(size)]

    def ancestor(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.ancestor(self.parents[i])
            return self.parents[i]

    def union(self, i, j):
        ip = self.ancestor(i)
        jp = self.ancestor(j)
        if ip == jp:
            return False
        else:
            if self.ranks[ip] > self.ranks[jp]:
                self.parents[jp] = ip
            else:
                self.parents[ip] = jp
                if self.ranks[ip] == self.ranks[jp]:
                    self.ranks[ip] += 1

    def same(self, i, j):
        return self.ancestor(i) == self.ancestor(j)

    def __str__(self):
        parentDict = { }
        for i in range(self.size):
            a = self.ancestor(i)
            if a not in parentDict:
                parentDict[a] = [i]
            else:
                parentDict[a].append(i)
        result = "===UnionFind description===\nSize:" + str(self.size) + "\nGroupCount:" + str(
            len(parentDict)) + "\n\nGroups:\n"
        for k in parentDict.keys():
            elements = ""
            for elem in parentDict[k]:
                elements += " " + str(elem) + ","
            result += "Group-"+str(k)+"(Count:"+str(len(parentDict[k]))+"):["+elements+"]\n"
        return result

def debug(s):
    if False:
        print(s)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    pst = set(get_sieve_of_eratosthenes(A[-1]))
    debug(f"Sorted: {A}")
    found = []
    c = 0
    i = 0
    while i < len(A):
        if i < len(A)-1 and A[i] == A[i+1]:
            found.append(A[i])
            ni = i+1
            while A[ni] == A[i]:
                if len(A)-1 == ni:
                    ni = len(A)
                    break
                ni += 1
            debug(f"i was skipped from {i} to {ni}")
            i = ni
            continue
        else:
            contained = False
            if A[i] not in pst:
                for f in found:
                    if A[i] % f == 0:
                        debug(f"{A[i]} was divided with {f}")
                        contained = True
                    break
            if not contained:
                debug(f"{A[i]} is not contained appending")
                c+=1
                found.append(A[i])
            i+=1
    print(c)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()