除了篩子之外的快速素數發生器

我最近做了這一點的代碼，但不知道是否有更快的方法來找到質數（不是篩子;我仍然試圖做到這一點）。有什麼建議？我使用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]

來源

2017-01-14 Emil

這裏是檢測是否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

和打印另一個實現質數<ň

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)

希望它能幫助！

來源

2017-01-14 23:47:48

謝謝，這真的是我需要的;） – Emil

正如

n = 10000 
for p in range(2, n+1): 
    for i in range(2, p): 
     if p % i == 0: 
      break 
    else: 
     print p 
print 'Done'

？

來源

2017-01-14 22:03:59 RnRoger

這似乎與我已經擁有的代碼相似 - 儘管 – Emil

更簡單，但可以通過將內循環設置爲範圍（2，p/2）來進一步改進，因爲對於i> p/2' p％i == 0'永遠不會發生。 –

這就是你要求的不是嗎？它是相似的，但無盡的更快。我花了半分鐘的時間用你的代碼達到201的素數。（沒有罪行） – RnRoger

如果你不使用篩子，那麼下一個最好的可能是wheel methods。之後，2輪檢查2和奇數。一個6輪檢查2,3和數字的形式（6n +/- 1），即沒有因子2或3的數字。上面的taoufik A的答案是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。

來源

2017-01-15 11:29:16 rossum

除了篩子之外的快速素數發生器

回答

相關問題