51–60 of 88 posts
{(~T∊T∘.×T)/T←1↓⍳⍵}
&2=+/~x!/:\:x:!100
The memory usage can in fact be optimized further with a small change: https://gist.github.com/scythe/5fb962722934c58c60430180beab8... In the spirit of the blog post, I'll let you guess how it works :p
q = 101
D = {'102': [3, 2], '105': [7, 5], '121': [11], '169': [13], '289': [17], '361': [19], '529': [23], '841': [29], '961': [31], '1369': [37], '1681': [41], '1849': [43], '2209': [47], '2809': [53], '3481': [59], '3721': [61], '4489': [67], '5041': [71], '5329': [73], '6241': [79], '6889': [83], '7921': [89], '9409': [97]}
q = 101
S = 121
r = 11
D = {'102': [3, 2], '105': [7, 5]}My favorite prime number generator is ┬─┬───────────────────────────────────┬──── ────┬ │ │ ┬─┬ ────┬─┬────────────────────── ┼───┬ ┬───┼ │ │ └─┤ ────┼─┼───────────────────┬── ┼───┼ │ ┬ │ │ │ │ ┬───┼─┼───────────────────┼── ┼─┬─┼ │ ┼ │ │ │ │ │ ─ ┼─┼─┬─────┬──── ──────┼─┬ │ ├─┘ └─┤ │ │ │ │ │ ┬ └─┤ │ ┬─┬ ┼─┬─┬ ──┬───┼─┼ ├─┘ ├─┘ │ │ │ └─┤ └─┤ └─┤ │ ├─┘ ──┼─┬─┼─┼ │ │ │ │ │ │ │ │ ├─┘ ┬─┼─┼─┼─┼ │ │ │ │ │ │ │ ├─┘ └─┤ │ ├─┘…
Could you explain it? Those two links are Greek to me.
> On Pi day 2023 I gave an online talk about AIT and BLC based on these slides.
Perhaps watching the linked-to talk will somewhat clarify matters.
The fastest variant I know of this algorithm is the one found at https://stackoverflow.com/a/3796442/6899 : import itertools as it def erat3( ): D = { 9: 3, 25: 5 } yield 2 yield 3 yield 5 MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) ) for q in it.compress( it.islice(it.count(7), 0, None, 2), it.cycle(MASK)): p = D.pop(q, None) if p is None: D[q*q] = q yield q…
isn't hardcoding 2 3 and 5 a bit of a cheat ? It seems like you could hardcode it to yield the X next primes and it'd be faster.
Hardcoding those values is a semi-requirement of the above technique.
My favorite prime number generator is ┬─┬───────────────────────────────────┬──── ────┬ │ │ ┬─┬ ────┬─┬────────────────────── ┼───┬ ┬───┼ │ │ └─┤ ────┼─┼───────────────────┬── ┼───┼ │ ┬ │ │ │ │ ┬───┼─┼───────────────────┼── ┼─┬─┼ │ ┼ │ │ │ │ │ ─ ┼─┼─┬─────┬──── ──────┼─┬ │ ├─┘ └─┤ │ │ │ │ │ ┬ └─┤ │ ┬─┬ ┼─┬─┬ ──┬───┼─┼ ├─┘ ├─┘ │ │ │ └─┤ └─┤ └─┤ │ ├─┘ ──┼─┬─┼─┼ │ │ │ │ │ │ │ │ ├─┘ ┬─┼─┼─┼─┼ │ │ │ │ │ │ │ ├─┘ └─┤ │ ├─┘…
Earlier quoted context omitted.
isn't hardcoding 2 3 and 5 a bit of a cheat ? It seems like you could hardcode it to yield the X next primes and it'd be faster.
The point isn’t hardcoding those numbers. The point is that you don’t iterate on any multiples of those numbers (which we know are composite) and doing allows us to eliminate 2/3 of the iterations. It’s an extension of enumerating over only odd numbers, which eliminates 1/2 of the iterations. Hardcoding those values is a semi-requirement of the above technique.
Can I just say how surprised I am the many people have a favourite prime number generator. I can’t say I have a favourite but I do enjoy multiplying two random prime numbers with each other and using the random result when I need a random number with added random.
That doesn't seem like a good way to generate "random" numbers, since it will only produce numbers with exactly two prime factors.
p_n = 1 + Sum_{i=1}^{2^n} Floor((n/(Sum_{j=1}^{i} Floor((Cos((j-1)!+1)/j) Pi)^2)))^(1/n))
https://en.wikipedia.org/wiki/Formula_for_primes
https://www.youtube.com/watch?v=j5s0h42GfvM
It's not fast but it really does work.
My favorite prime number generator is ┬─┬───────────────────────────────────┬──── ────┬ │ │ ┬─┬ ────┬─┬────────────────────── ┼───┬ ┬───┼ │ │ └─┤ ────┼─┼───────────────────┬── ┼───┼ │ ┬ │ │ │ │ ┬───┼─┼───────────────────┼── ┼─┬─┼ │ ┼ │ │ │ │ │ ─ ┼─┼─┬─────┬──── ──────┼─┬ │ ├─┘ └─┤ │ │ │ │ │ ┬ └─┤ │ ┬─┬ ┼─┬─┬ ──┬───┼─┼ ├─┘ ├─┘ │ │ │ └─┤ └─┤ └─┤ │ ├─┘ ──┼─┬─┼─┼ │ │ │ │ │ │ │ │ ├─┘ ┬─┼─┼─┼─┼ │ │ │ │ │ │ │ ├─┘ └─┤ │ ├─┘…