leetcode-challenges/0204_count_primes.py at master · vdumchiviy/leetcode-challenges · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
"""
204. Count Primes
Medium
Given an integer n, return the number of prime numbers that are strictly less than n.


Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:
Input: n = 0
Output: 0

Example 3:
Input: n = 1
Output: 0


Constraints:

0 <= n <= 5 * 10*6
    """
from math import sqrt
from datetime import datetime


def get_timer(func):
    def _wrapper(*args, **kwargs):
        time1 = datetime.now()
        result = func(*args, **kwargs)
        time2 = datetime.now()
        print(f'time delta for n= {args[1]} is {(time2-time1)}')
        return result
    return _wrapper


class Solution:

    @get_timer
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        cito = [(key <= 2 or key % 2 != 0) and (key <= 5 or key % 5 != 0)
                for key in range(0, n)]
        cito[0] = cito[1] = False

        # There are no need to check for prime values if (current) > sqrt(n)
        for current in range(2, int(sqrt(n)+1)):
            # exclude prime from the list
            if cito[current]:
                # set to False each + current value started from current**2
                cito[current ** 2: n: current] = [False] * \
                    len(cito[current ** 2: n: current])
        return sum(cito)

    @get_timer
    def countPrimes_v3(self, n: int) -> int:
        if n <= 2:
            return 0
        cito = {key: True
                for key in range(2, n) if (key <= 2 or key % 2 != 0) and (key <= 5 or key % 5 != 0)
                }
        for current in range(3, n):
            quad_current = current * current
            if quad_current >= n:
                break

            mult = 0
            check_value = quad_current + current * mult
            while check_value < n:
                if (check_value % 2 == 0) or (check_value > 5 and check_value % 5 == 0):
                    pass
                elif cito.get(check_value, False):
                    del cito[check_value]
                mult += 1
                check_value = quad_current + current * mult
        return len(cito)

    def countPrimes_v2(self, n: int) -> int:
        primes: list = [2]
        if n <= 2:
            return 0
        for current in range(3, n):
            # skip 6 of each 10 values
            if current % 2 == 0 or (current >= 10 and current % 5 == 0):
                continue
            else:
                # I check only until the prime value < sqrt(current)
                max_current_sqrt = int(sqrt(current))
                pos = 0
                flag = False
                while primes[pos] <= max_current_sqrt:
                    if current % primes[pos] == 0:
                        flag = True
                        break
                    pos += 1
                if not flag:
                    primes.append(current)
        return len(primes)

    def countPrimes_v1(self, n: int) -> int:
        primes: list = [2]
        if n <= 2:
            return 0
        current = 3
        while current < n:
            # if current couldn't devide without rest for all previous primes..
            if current % 2 != 0 and not any(filter(lambda prime_in_list: current % prime_in_list == 0, primes)):
                primes.append(current)
            current += 1

        return len(primes)


sol = Solution()

assert sol.countPrimes(5000000) == 348513
assert sol.countPrimes(499979) == 41537
assert sol.countPrimes(10) == 4
assert sol.countPrimes(30) == 10
assert sol.countPrimes(29) == 9
assert sol.countPrimes(0) == 0
assert sol.countPrimes(1) == 0
assert sol.countPrimes(2) == 0
assert sol.countPrimes(3) == 1