Python простых числа выход генератор против возвращения

Question

Ищет питон генератор простых чисел, я нашел:

def primes(n): 
    if n==2: return [2] 
    elif n<2: return [] 
    s=range(3,n+1,2) 
    mroot = n ** 0.5 
    half=(n+1)/2-1 
    i=0 
    m=3 
    while m <= mroot: 
     if s[i]: 
      j=(m*m-3)/2 
      s[j]=0 
      while j<half: 
       s[j]=0 
       j+=m 
     i=i+1 
     m=2*i+3 
    return [2]+[x for x in s if x] 

print primes(13) 
print primes(3000) 

, а также:

def get_primes(number): 
    while True: 
     if is_prime(number): #is_prime is defined somewhere else 
      yield number 
     number += 1 

Что более эффективно, возвращающего список или команду выхода? Зачем? Подумайте, я ищу очень большое количество простых чисел, например, первые 1000 простых чисел. Кстати, второй код кажется бесконечным циклом, как его остановить?

Спасибо и извините за так много вопросов.

Answer 1

Это действительно зависит от того, что вы хотите сделать со списком простых чисел.

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

В любом случае, я не думаю, что это был ваш вопрос. Вы действительно ищете разницу между нормальной функцией Python и генератором. На SO есть много вопросов и много документации, которые дают хорошее объяснение того, что такое генератор.

This появился на боковой панели, когда я смотрел на ваш вопрос, и я думаю, что это было бы полезно. Или просто выполните поиск документов для «генератора».

Быстрое объяснение заключается в том, что ваша первая функция возвращает список простых чисел до n. После того, как у вас есть этот список, вы можете получить доступ к любому его члену, когда захотите, вызвать функцию во всем списке и т. Д. Второй подход - это генератор. Он не возвращает список - это возвращает итератор, который приступает к следующему премьеру по требованию. Поэтому, если вам нужны простые числа за раз, чтобы, возможно, вызвать функцию на каждом из них, итератор может быть хорошим. Однако, если вам нужно получить доступ к простым числам по требованию, это не будет сделано.

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

Например:

for prime in get_primes(2): 
    if meets_condition(prime): 
     return prime 

будет лучше:

primeList = primes(1000) 
for prime in primeList: 
    if meets_condition(prime): 
     return prime 

Если п мала, но если n находится где-то близко к 1000.

Gotta go, извините. Я буду расширять и проверять это позже. Посмотрите генераторы и премьерные сита!

Если вы работаете над проблемой projecteuler.com, я собираюсь идти дальше и догадываться, что сито будет работать лучше.