Генератор Fast Prime помимо сита

Недавно я сделал этот фрагмент кода, но мне интересно, есть ли более быстрый способ найти простые числа (не сито; я все еще пытаюсь это сделать). Любой совет? Я использую Python, и я довольно новичок в этом.

def isPrime(input):
    current = 0
    while current < repetitions:
        current = current + 2
        if int(input) % current == 0:
            if not current == input:
                return "Not prime."
            else:
                return "Prime"
        else:
            print current

    return "Prime"

i = 1
primes = []
while len(primes) < 10001:
    repetitions = int(i)-1
    val = isPrime(i)
    if val == "Prime":
        primes.append(i)
    i = i + 2
print primes[10000]

python primes sieve
person Emil    schedule 14.01.2017    source источник

Ответы (3)


arrow_upward
2
arrow_downward

вот функция, которая определяет, является ли x простым или нет

def is_prime(x):
    if x == 1 or x==0:
        return False
    elif x == 2:
        return True
    if x%2 == 0:
        return False
    for i in range(3, int((x**0.5)+1), 2):
        if x%i == 0:
            return False
    return True

и другая реализация, которая печатает простые числа ‹ n

def prime_range(n):
    print(2)
    for x in range(3, n, 2):
        for i in range(3, int((x**0.5)+1), 2):
            if x%i == 0:
                break
        else:
            print(x)

Надеюсь, поможет !

person taoufik A    schedule 14.01.2017

arrow_upward
1
arrow_downward

Если вы не используете сито, то лучшим вариантом, вероятно, будут методы колеса. 2-колесо проверяет 2 и нечетные числа после этого. 6-колесо проверяет 2, 3 и числа в форме (6n +/- 1), то есть числа без множителей 2 или 3. Ответ от тауфика А выше - 2-колесо.

Я не умею писать на Python, поэтому вот псевдокод для 6-колесной реализации:

function isPrime(x) returns boolean

  if (x <= 1) then return false

  // A 6-wheel needs separate checks for 2 and 3.
  if (x MOD 2 == 0) then return x == 2
  if (x MOD 3 == 0) then return x == 3

  // Run the wheel for 5, 7, 11, 13, ...
  step <- 4
  limit <- sqrt(x)
  for (i <- 5; i <= limit; i <- i + step) do
    if (x MOD i == 0) then return false
    step <- (6 - step)  // Alternate steps of 2 and 4.
  end for

  return true

end function

Я оставляю вам преобразовать это в Python.

person rossum    schedule 15.01.2017

arrow_upward

arrow_downward

person    schedule
comment
Это похоже на код, который у меня уже был, но более простой. - person Emil; 15.01.2017
comment
его можно улучшить, сделав внутренний цикл range(2,p/2), поскольку for i > p/2 p%i==0 никогда не произойдет. - person jack jay; 15.01.2017
comment
Это то, о чем вы просите, не так ли? Это похоже, но бесконечно быстрее. Мне потребовалось полминуты, чтобы добраться до простого числа 201 с помощью вашего кода. (без обид) - person RnRoger; 15.01.2017
comment
@jackjay Должно быть range(2, p//2 + 1). В противном случае, например, он говорит, что 4 — простое число. - person Tagc; 15.01.2017
comment
@jackjay Тот факт, что он исключает остановку, является точной причиной, по которой вам нужно использовать p//2 + 1. Предположим, что p равно 4. Что даст range(2, 4//2)? - person Tagc; 15.01.2017
comment
вы также можете уменьшить до sqrt(p+1). - person jack jay; 15.01.2017
comment
Вы можете почерпнуть некоторые идеи из этого поста: dreamincode.net/forums/blog/1748/ - person Jon Kiparsky; 15.01.2017