The sieve of Sundaram: Difference between revisions
→{{header|Python}}: Added a functional variant.
(→{{header|Python}}: Added a functional variant.) |
|||
Line 451:
=={{header|Python}}==
===Python :: Procedural===
<lang python>from numpy import log
Line 503 ⟶ 504:
Sundaram primes start with 3. The 1000000th Sundaram prime is 15485867.
</pre>
===Python :: Functional===
Composing functionally, and obtaining slightly better performance by defining a set (rather than list) of exclusions.
<lang python>'''Sieve of Sundaram'''
from math import floor, log, sqrt
from itertools import islice
# nPrimesBySundaram :: Int -> [Int]
def nPrimesBySundaram(n):
'''First n primes, by sieve of Sundaram.
'''
return list(islice(
sundaram(
# Probable limit
int((2.4 * n * log(n)) // 2)
),
int(n)
))
# sundaram :: Int -> [Int]
def sundaram(n):
'''Sundaram prime numbers up to n'''
m = (n - 1) // 2
exclusions = {
2 * i * j + i + j
for i in range(1, 1 + floor(sqrt(m / 2)))
for j in range(
i, 1 + floor((m - i) / (1 + (2 * i)))
)
}
return [
1 + (2 * x) for x in range(1, 1 + m)
if not x in exclusions
]
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''First 100 Sundaram primes,
and millionth Sundaram prime.
'''
print("First hundred Sundaram primes, starting at 3:\n")
print(table(10)([
str(s) for s in nPrimesBySundaram(100)
]))
print("\n\nMillionth Sundaram prime, starting at 3:")
print(
f'\n\t{nPrimesBySundaram(1E6)[-1]}'
)
# ----------------------- GENERIC ------------------------
# chunksOf :: Int -> [a] -> [[a]]
def chunksOf(n):
'''A series of lists of length n, subdividing the
contents of xs. Where the length of xs is not evenly
divisible, the final list will be shorter than n.
'''
def go(xs):
return (
xs[i:n + i] for i in range(0, len(xs), n)
) if 0 < n else None
return go
# table :: Int -> [String] -> String
def table(n):
'''A list of strings formatted as
right-justified rows of n columns.
'''
def go(xs):
w = len(xs[-1])
return '\n'.join(
' '.join(row) for row in chunksOf(n)([
s.rjust(w, ' ') for s in xs
])
)
return go
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>First hundred Sundaram primes, starting at 3:
3 5 7 11 13 17 19 23 29 31
37 41 43 47 53 59 61 67 71 73
79 83 89 97 101 103 107 109 113 127
131 137 139 149 151 157 163 167 173 179
181 191 193 197 199 211 223 227 229 233
239 241 251 257 263 269 271 277 281 283
293 307 311 313 317 331 337 347 349 353
359 367 373 379 383 389 397 401 409 419
421 431 433 439 443 449 457 461 463 467
479 487 491 499 503 509 521 523 541 547
Millionth Sundaram prime, starting at 3:
15485867</pre>
=={{header|REXX}}==
| |||