эффективно найти простые числа в определенном диапазоне - PullRequest
Новая
       15

эффективно найти простые числа в определенном диапазоне

2 голосов
/ 24 июня 2011

Это код, который я нашел для Sieve of Eratosthenes для python3.Что я хочу сделать, так это отредактировать его, чтобы я мог ввести диапазон снизу и сверху, а затем ввести список простых чисел до нижнего, и он выведет список простых чисел в этом диапазоне.Однако я не совсем уверен, как это сделать.Если вы можете помочь, это будет с благодарностью. 

from math import sqrt
def sieve(end):  
    if end < 2: return []  

    #The array doesn't need to include even numbers  
    lng = ((end//2)-1+end%2)  

    # Create array and assume all numbers in array are prime  
    sieve = [True]*(lng+1)  

    # In the following code, you're going to see some funky  
    # bit shifting and stuff, this is just transforming i and j  
    # so that they represent the proper elements in the array.  
    # The transforming is not optimal, and the number of  
    # operations involved can be reduced.  

    # Only go up to square root of the end  
    for i in range(int(sqrt(end)) >> 1):  

        # Skip numbers that aren’t marked as prime  
        if not sieve[i]: continue  

        # Unmark all multiples of i, starting at i**2  
        for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3):  
            sieve[j] = False  

    # Don't forget 2!  
    primes = [2]  

    # Gather all the primes into a list, leaving out the composite numbers  
    primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]])  

    return primes

Ответы [ 4 ]

2 голосов
/ 24 июня 2011

Эта проблема известна как «сегментированное сито Эратосфена».Google дает несколько полезных ссылок.

2 голосов
/ 24 июня 2011

Я думаю, что работает следующее: 

def extend_erathostene(A, B, prime_up_to_A):
    sieve = [ True ]* (B-A)
    for p in prime_up_to_A:
        # first multiple of p greater than A
        m0 = ((A+p-1)/p)*p
        for m in range( m0, B, p):
            sieve[m-A] = False
    limit = int(ceil(sqrt(B)))
    for p in range(A,limit+1):
        if sieve[p-A]:
            for m in range(p*2, B, p):
                sieve[m-A] = False 
    return prime_up_to_A + [ A+c for (c, isprime) in enumerate(sieve) if isprime]
0 голосов
/ 24 июня 2011

Один из способов - запустить код сита с помощью end = top и изменить последнюю строку, чтобы получить только цифры больше нижнего:

Если диапазон мал по сравнению с его величиной (т. Е. Верх-низ мал по сравнению с дном), то лучше использовать другой алгоритм:

Начните снизу и переберите нечетные числа, проверяя, просты ли они. Вам нужна функция isprime (n), которая просто проверяет, делится ли n на все нечетные числа от 1 до sqrt (n): 

def isprime(n):
    i=2
    while (i*i<=n):
        if n%i==0: return False
        i+=1
    return True
0 голосов
/ 24 июня 2011

У вас уже есть простые числа от 2 до end, поэтому вам просто нужно отфильтровать возвращаемый список.

...