ВходНаше всё Теги codebook 无线电组件 Поиск Опросы Закон Четверг
14 ноября
1174516 Топик полностью
framer (15.02.2022 13:23, просмотров: 324) ответил cheblin на нужно было это мне сразу запостить
Это что такое? 
 def run_sieve(self):

        """Calculate the primes up to the specified limit"""

        factor = 1

        # sqrt doesn't seem to make any difference in CPython,
        # but works much faster than "x**.5" in Pypy
        q = sqrt(self._size) / 2

        bits_view = self._bits[factor:]
        while factor <= q:
            for v in bits_view.flat:
                if v:
                    break
                factor += 1

            bits_view = self._bits[factor + 1:]

            # If marking factor 3, you wouldn't mark 6 (it's a mult of 2) so start with the 3rd instance of this factor's multiple.
            # We can then step by factor * 2 because every second one is going to be even by definition
            factor2 = 2 * factor
            start = factor2 * (factor + 1) - factor - 1
            step = factor2 + 1

            # mark non-primes in sieve
            bits_view[start::step] = False

            factor += 1

Passes: 61162, Time: 5.0000186, Avg: 8.17504103855335e-05, Limit: 100000

Закладывают таблицу на количество чисел и итерируют. Такое впечатление, что они пытхон не осилили.


А теперь пусть попробуют так:

   def run_sieve1(self):
            upto = self.prime_counts[self._size]
            f = filter(lambda num: np.array([num % factor for factor in range(2,1+int(sqrt(num)))]).all(), range(2,upto+1))

и пересчитают

Passes: 1216969, Time: 5.0000018, Avg: 4.108569569150898e-06, Limit: 100000