Как напечатать простые числа в Python без использования цикла for и while

Question

Что я пробовал:

for num in range(2,50):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print (num)

Результат был хорошим, но его нельзя использовать для циклов или в любом случае, так, есть ли другой способ сделать это без использования циклов for или while?

Answer 1

Это дает вам все простые числа до t без использования внешних библиотек или циклов for / while.

t=1000

a=set(range(2,t))
l=map(lambda c:range(2*c,t,c),a)
result=a.difference(*l)

print(sorted(result))

Это тоже не слишком медленно:

>>> Calculating primes up to 1 took 2.599999999997049e-05 seconds
>>> Calculating primes up to 10 took 4.6000000000101515e-05 seconds
>>> Calculating primes up to 100 took 0.00015300000000006975 seconds
>>> Calculating primes up to 1000 took 0.001670999999999978 seconds
>>> Calculating primes up to 10000 took 0.023809999999999998 seconds
>>> Calculating primes up to 100000 took 0.24447599999999992 seconds
>>> Calculating primes up to 1000000 took 3.301934 seconds
>>> Calculating primes up to 10000000 took 42.691604 seconds

При использовании 100000000 выдается ошибка памяти

Answer 2

Это моя доработка решения @ MihaiAlexandru-Ionut, которое может вычислить в 3 раза больше, прежде чем запускать пакет стека Python по умолчанию, исключая простое тестирование четных чисел и останавливая простое тестирование в квадратном корне вместо 1/2 от цель:

def find_primes(n, i=2):

    primes = []

    if i > n:
        return primes

    def is_odd_prime(n, d=3):
        if n < d * d:
            return True

        if n % d == 0:
            return False

        return is_odd_prime(n, d + 2)

    multi = i != 2

    if not multi or is_odd_prime(i):
        primes.append(i)

    return primes + find_primes(n, i + 1 + multi)

print(find_primes(1960))

До сих пор нет места (эффективность стека) ситового раствора @ PM2Ring!

Answer 3

Вот рекурсивная реализация Сита из Эратосфена . Для выполнения основного шага просеивания используется расширенное назначение срезов. При больших числах он не будет работать с RecursionError, но с настройками по умолчанию он может безопасно вычислять простые числа до 990000 или около того. Это не так быстро, как более обычная итеративная версия этого кода, но это немного быстрее, чем простой поиск фактора грубой силы.

def rsieve(i, num, stop, seq):
    if i == stop:
        return
    if seq[i]:
        seq[i*i : num : i] = [False] * (1 + (num - 1)//i - i)
    rsieve(i + 1, num, stop, seq)

def primes(num):
    seq = [True] * num
    seq[:2] = [False] * 2
    rsieve(2, num, int(num ** 0.5) + 1, seq)
    return filter(lambda i: seq[i], range(num))

# Test
print(*primes(100))

выход

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

---

FWIW, вы можете заставить этот код выполняться почти вдвое быстрее, заменив аргумент функции lambda на filter прямым вызовом seq.__getitem__ «магического» метода. То есть

return filter(seq.__getitem__, range(num))

Обычно считается плохой практикой вызывать "магические" методы напрямую, поэтому, пожалуйста, , а не , делайте это, если только вы не понимаете, что делаете. ;)

Answer 4

Это глупо, но это работает, так что, возможно, это, по крайней мере, даст вам некоторые идеи:

print(list(filter(lambda x: not list(filter(lambda y:x%y == 0, range(2,x))), range(2, 50))))

Выходы:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Answer 5

Это решает печать списка, по одному разу, каждый на новой строке - без for loop. Что касается списка простых чисел, вы можете обмануть.

Ничто в вашем вопросе не говорит о том, что вы должны их вычислять. Примелисты могут получить до нескольких миллионов от межсетевых сетей - вместо того, чтобы сканировать какой-либо сайт и получать их там, ваш простой случай может быть жестко закодирован.

print( *[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47], sep = '\n')

Выход:

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

Все простые числа до 50 - для циклов нет.

Answer 6

Есть ли другой способ сделать это без использования циклов for или while?

Да, вы можете использовать рекурсивную функцию:

def prime_number(n, d):
    if n//2 < d:
      return True
    if n%d == 0:
      return False
    return prime_number(n, d+1)

def find_primes(n,i, result):
  if i == n + 1:
    return result
  if prime_number(i, 2):
    result.append(i)
  return find_primes(n, i+1, result)

print(find_primes(100,2, []))

выход

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Кроме того, вы можете упростить for loops, используя list comprehension.

primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))]