寻找 m 下的 n 个最大素数
Finding the n largest primes under m
下面的算法是我在Python中实现的埃拉托色尼筛法。该算法找到给定值前的第一个素数，即 n.
该算法的工作方式是打印从 2 到 n 的所有素数。我想要做的是相反的方式，即从 n 开始向下到 m，或者一些随机切片，例如最大的 100 个数字。因此，例如..如果我有一个很大的数字（例如2亿），我将能够打印2亿中最大的100个素数（不是来自第2亿个素数，而是一个相等的素数TO/LESS 超过 2 亿！）。
有人可以帮忙吗？
def primes(n):
array = [i for i in range(2,n+1)]
p = 2
while p <= n:
i = 2*p
while i <= n:
array[i-2] = 0
i += p
p += 1
return [num for num in array if num > 0]
没有运行代码。它应该工作，但在需要的地方改变。我只是发布它给你直觉。
def primes(n):
array = [1 for i in range(0,n)]
array[0] = 0
array[1] = 0
p = 2
while p <= n:
i = 2*p
while i <= n:
array[i] = 0
i += p
p += 1
while (array[p] == 0):
p += 1
result = []
i = 0
while i <= n:
if array[i]==1:
result.append(i)
i += 1
return result
def primes(n):
p = n/2
return (n%i for i in range(2, p+1))
def test_primes(n, n_largest):
ret = (k for k in range(n, 0, -1) if all(primes(k)))
return [ret.next() for v in range(n_largest)]
用法
>>print test_primes(20, 2)
[17, 19]
求
下的n大数
函数 "primes" 得到一个元素除以小于其中间部分的所有元素的剩余部分，然后 "test_primes" 测试所有这些剩余部分是否为 0。如果所有其余的都不为 0 那么这个元素是一个质数所以我们打印它
这是一种方法：
def largest_primes_under(number, cap):
n = cap - 1
while number and n >= 2:
if all(n % d for d in range(2, int(n ** 0.5 + 1))):
yield n
number -= 1
n -= 1
演示：
for p in largest_primes_under(10, 10**9):
print(p)
输出：
999999937
999999929
999999893
999999883
999999797
999999761
999999757
999999751
999999739
999999733
这是我在评论中链接到的范围筛选程序的修改版本。它使用 prime number theorem to get an approximation of the density of primes near hi and uses that density to estimate lo such that the number of primes in range(lo, hi) >= num. For further info please see the Mathworld article on the Prime Counting Function.
通常，没有简单的方法可以准确估计给定范围内的素数数量。 FWIW，在特殊情况下很容易证明给定范围内没有素数，例如 range(n! + 2, n! + n + 1) 中的每个数字都可以被 range(2, n + 1) 中的数字清楚地整除。
下面的代码（希望 :)）高估了所需的范围。但是我们不希望它使用太低的 lo 值来浪费时间。在某些情况下，lo 不够小，尤其是当 num 非常小时，但如果您对 num 使用合理的值应该没问题。
#! /usr/bin/env python
''' Prime range sieve.
Written by PM 2Ring 2014.10.15
2015.05.24 Modified to find the `num` highest primes < `hi`
'''
import sys
from math import log
def potential_primes():
''' Make a generator for 2, 3, 5, & thence all numbers coprime to 30 '''
s = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
for i in s:
yield i
s = (1,) + s[3:]
j = 30
while True:
for i in s:
yield j + i
j += 30
def range_sieve(lo, hi):
''' Create a list of all primes in the range(lo, hi) '''
#Mark all numbers as prime
primes = [True] * (hi - lo)
#Eliminate 0 and 1, if necessary
for i in range(lo, min(2, hi)):
primes[i - lo] = False
ihi = int(hi ** 0.5)
for i in potential_primes():
if i > ihi:
break
#Find first multiple of i: i >= i*i and i >= lo
ilo = max(i, 1 + (lo - 1) // i ) * i
#Determine how many multiples of i >= ilo are in range
n = 1 + (hi - ilo - 1) // i
#Mark them as composite
primes[ilo - lo : : i] = n * [False]
return [i for i,v in enumerate(primes, lo) if v]
def main():
hi = int(sys.argv[1]) if len(sys.argv) > 1 else 1000000
num = int(sys.argv[2]) if len(sys.argv) > 2 else 1000
#Estimate required range using the prime number theorem
#The constant 1.25506 is from the MathWorld article on
#the Prime Counting Function
d = num * log(hi) * 1.25506
#An alternate estimator. Sometimes estimates a little too low.
#d = num * (log(hi) + log(log(hi)))
lo = max(2, hi - int(d))
print 'lo =', lo
primes = range_sieve(lo, hi)
print len(primes), 'primes found'
for i, p in enumerate(reversed(primes[-num:]), 1): print '%2d: %d' % (i, p)
if __name__ == '__main__':
main()
output 当用 $ python range_sieve.py 1234567890 60
调用时
lo = 1234566314
67 primes found
1: 1234567811
2: 1234567801
3: 1234567799
4: 1234567783
5: 1234567759
6: 1234567723
7: 1234567717
8: 1234567679
9: 1234567669
10: 1234567583
11: 1234567571
12: 1234567553
13: 1234567517
14: 1234567469
15: 1234567361
16: 1234567337
17: 1234567309
18: 1234567303
19: 1234567291
20: 1234567289
21: 1234567267
22: 1234567261
23: 1234567249
24: 1234567223
25: 1234567181
26: 1234567171
27: 1234567151
28: 1234567129
29: 1234567097
30: 1234567093
31: 1234567069
32: 1234567063
33: 1234567007
34: 1234566997
35: 1234566959
36: 1234566953
37: 1234566947
38: 1234566899
39: 1234566887
40: 1234566863
41: 1234566769
42: 1234566761
43: 1234566737
44: 1234566713
45: 1234566691
46: 1234566677
47: 1234566643
48: 1234566601
49: 1234566581
50: 1234566559
51: 1234566547
52: 1234566533
53: 1234566527
54: 1234566521
55: 1234566499
56: 1234566497
57: 1234566491
58: 1234566481
59: 1234566479
60: 1234566467
下面的算法是我在Python中实现的埃拉托色尼筛法。该算法找到给定值前的第一个素数，即 n.
该算法的工作方式是打印从 2 到 n 的所有素数。我想要做的是相反的方式，即从 n 开始向下到 m，或者一些随机切片，例如最大的 100 个数字。因此，例如..如果我有一个很大的数字（例如2亿），我将能够打印2亿中最大的100个素数（不是来自第2亿个素数，而是一个相等的素数TO/LESS 超过 2 亿！）。
有人可以帮忙吗？
def primes(n):
array = [i for i in range(2,n+1)]
p = 2
while p <= n:
i = 2*p
while i <= n:
array[i-2] = 0
i += p
p += 1
return [num for num in array if num > 0]
没有运行代码。它应该工作，但在需要的地方改变。我只是发布它给你直觉。
def primes(n):
array = [1 for i in range(0,n)]
array[0] = 0
array[1] = 0
p = 2
while p <= n:
i = 2*p
while i <= n:
array[i] = 0
i += p
p += 1
while (array[p] == 0):
p += 1
result = []
i = 0
while i <= n:
if array[i]==1:
result.append(i)
i += 1
return result
def primes(n):
p = n/2
return (n%i for i in range(2, p+1))
def test_primes(n, n_largest):
ret = (k for k in range(n, 0, -1) if all(primes(k)))
return [ret.next() for v in range(n_largest)]
用法
>>print test_primes(20, 2)
[17, 19]
求
下的n大数函数 "primes" 得到一个元素除以小于其中间部分的所有元素的剩余部分，然后 "test_primes" 测试所有这些剩余部分是否为 0。如果所有其余的都不为 0 那么这个元素是一个质数所以我们打印它
这是一种方法：
def largest_primes_under(number, cap):
n = cap - 1
while number and n >= 2:
if all(n % d for d in range(2, int(n ** 0.5 + 1))):
yield n
number -= 1
n -= 1
演示：
for p in largest_primes_under(10, 10**9):
print(p)
输出：
999999937
999999929
999999893
999999883
999999797
999999761
999999757
999999751
999999739
999999733
这是我在评论中链接到的范围筛选程序的修改版本。它使用 prime number theorem to get an approximation of the density of primes near hi and uses that density to estimate lo such that the number of primes in range(lo, hi) >= num. For further info please see the Mathworld article on the Prime Counting Function.
通常，没有简单的方法可以准确估计给定范围内的素数数量。 FWIW，在特殊情况下很容易证明给定范围内没有素数，例如 range(n! + 2, n! + n + 1) 中的每个数字都可以被 range(2, n + 1) 中的数字清楚地整除。
下面的代码（希望 :)）高估了所需的范围。但是我们不希望它使用太低的 lo 值来浪费时间。在某些情况下，lo 不够小，尤其是当 num 非常小时，但如果您对 num 使用合理的值应该没问题。
#! /usr/bin/env python
''' Prime range sieve.
Written by PM 2Ring 2014.10.15
2015.05.24 Modified to find the `num` highest primes < `hi`
'''
import sys
from math import log
def potential_primes():
''' Make a generator for 2, 3, 5, & thence all numbers coprime to 30 '''
s = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
for i in s:
yield i
s = (1,) + s[3:]
j = 30
while True:
for i in s:
yield j + i
j += 30
def range_sieve(lo, hi):
''' Create a list of all primes in the range(lo, hi) '''
#Mark all numbers as prime
primes = [True] * (hi - lo)
#Eliminate 0 and 1, if necessary
for i in range(lo, min(2, hi)):
primes[i - lo] = False
ihi = int(hi ** 0.5)
for i in potential_primes():
if i > ihi:
break
#Find first multiple of i: i >= i*i and i >= lo
ilo = max(i, 1 + (lo - 1) // i ) * i
#Determine how many multiples of i >= ilo are in range
n = 1 + (hi - ilo - 1) // i
#Mark them as composite
primes[ilo - lo : : i] = n * [False]
return [i for i,v in enumerate(primes, lo) if v]
def main():
hi = int(sys.argv[1]) if len(sys.argv) > 1 else 1000000
num = int(sys.argv[2]) if len(sys.argv) > 2 else 1000
#Estimate required range using the prime number theorem
#The constant 1.25506 is from the MathWorld article on
#the Prime Counting Function
d = num * log(hi) * 1.25506
#An alternate estimator. Sometimes estimates a little too low.
#d = num * (log(hi) + log(log(hi)))
lo = max(2, hi - int(d))
print 'lo =', lo
primes = range_sieve(lo, hi)
print len(primes), 'primes found'
for i, p in enumerate(reversed(primes[-num:]), 1): print '%2d: %d' % (i, p)
if __name__ == '__main__':
main()
output 当用 $ python range_sieve.py 1234567890 60
lo = 1234566314
67 primes found
1: 1234567811
2: 1234567801
3: 1234567799
4: 1234567783
5: 1234567759
6: 1234567723
7: 1234567717
8: 1234567679
9: 1234567669
10: 1234567583
11: 1234567571
12: 1234567553
13: 1234567517
14: 1234567469
15: 1234567361
16: 1234567337
17: 1234567309
18: 1234567303
19: 1234567291
20: 1234567289
21: 1234567267
22: 1234567261
23: 1234567249
24: 1234567223
25: 1234567181
26: 1234567171
27: 1234567151
28: 1234567129
29: 1234567097
30: 1234567093
31: 1234567069
32: 1234567063
33: 1234567007
34: 1234566997
35: 1234566959
36: 1234566953
37: 1234566947
38: 1234566899
39: 1234566887
40: 1234566863
41: 1234566769
42: 1234566761
43: 1234566737
44: 1234566713
45: 1234566691
46: 1234566677
47: 1234566643
48: 1234566601
49: 1234566581
50: 1234566559
51: 1234566547
52: 1234566533
53: 1234566527
54: 1234566521
55: 1234566499
56: 1234566497
57: 1234566491
58: 1234566481
59: 1234566479
60: 1234566467