solve.py

import math


class Solver:

    _found_primes = set()

    def _is_prime(self, num):
        # jeżeli jest już pierwszą to nie szukaj dalej, O(1)
        if num in self._found_primes:
            return True

        if num in [0, 1]:
            return False

        # jeżeli parzysta to nie szukaj dalej
        if num > 2 and num % 2 == 0:
            return False

        # jeśli nie jest pierwsza to zachodzi faktoryzacja przez liczby pierwsze,
        # więc jeśli znaleziono już jakąś liczbę pierwszą to istnieje możliwość
        # rozstrzygnięcia szybciej o innych
        for prime in self._found_primes:
            if num % prime == 0:
                return False

        # jeśli nie wiadomo jaka to liczba to sprawdzaj wszystkie nieparzyste aż
        # do pierwsiatka z liczby, ponieważ jeśli żadna liczba mniejsza od pierwiastka nie
        # dzieli liczby to liczba jest pierwsza
        num_sqrt = int(math.sqrt(num)) + 1
        current = 3
        while current < num_sqrt:
            if num % current == 0:
                return False
            current += 2
        # zapisz jeśli jest liczbą pierwszą
        self._found_primes.add(num)

        return True

    def solve(self, list_a, list_b):
        list_c = list()
        count_of_b_items = dict()

        for item in list_b:
            count_of_b_items[item] = 0

        for item in list_b:
            count_of_b_items[item] += 1

        for item in list_a:
            count_of_item = count_of_b_items.get(item)
            if count_of_item is None:
                count_of_item = 0

            if not self._is_prime(count_of_item):
                list_c.append(item)

        return list_c


A = [2, 3, 9, 2, 5, 1, 3, 7, 10]
B = [2, 1, 3, 4, 3, 10, 6, 6, 1, 7, 10, 10, 10]
solver = Solver()
print(solver.solve(A, B))

"""
- złożoność algorytmu to O(n^2)
- pobranie elementu z słownika: O(1)
- sprawdzenie czy element istnieje w słowniku: O(1)
- sprawdzenie czy element istnieje w zbiorze: O(1)
- w funkcji is_prime() zapisuję znalezione liczby pierwsze ponieważ przy większej 
  ilości elementów w liście może to przyśpieszyć proces rozstrzygania 
  o byciu liczbą pierwszą
- istnieje możliwość przyśpieszenia algorytmu rozstrzygania o byciu liczbą pierwszą 
  po przez zastosowaniu testu Millera-Rabina, lecz jest on algorytmem probablistycznym
"""