寻找质数 kdb，关于投影和函数的讨论
Finding prime numbers kdb, discussion about projection and functions
所以我正在尝试创建一个函数来查找低于某个数字的所有质数。
这是我编写的代码，它不起作用，但可以帮助我解释我是如何尝试解决它的。我稍后会修复 0,1,2 的手动检查。
primes: enlist 2
g: h[;primes]
g'[3 + til 100-2]
h:{[x;y] z: x mod/: y; bool:(0 in z)=0b; if[bool; `primes set primes,x ]; }
所以我想做的是，对 3+ til 100-2 中的每个元素使用每个 (') 运算符来 运行 这个函数 h。但是，我希望它继续使用 primes 变量，而不是以 each 的方式。如果 z 中没有 0，则 if 语句将执行，因为这意味着 x 是质数。然后在 if 语句中，我想将 x 加入素数列表。
循环 1：x:3 y: enlist 2
在 if 语句中，它将 3 连接到 primes
循环 2：x:4 y: 2 3
if 语句不会执行
循环 3：x:5 y: 2 3
在 if 语句中，它将 5 连接到 primes
循环 4：x:6 y: 2 3 5
if 语句不会执行
感谢您的帮助！
您的逻辑可行，可以稍微整理一下：
q)primes:enlist 2
q)h:{m:x mod/:primes;bool:(0 in m)=0b;if[bool;`primes set primes,x];}
q)h'[3 + til 100-2];
q)primes
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
与您的一些不同之处：
- 如果您使用输入
primes 投影 h，例如g:h[;primes] 那么 primes 输入在那个时间点是固定的，每次迭代都不会改变。所以你的函数中的 y 总是固定在 2.
在这个例子中，我通过简单地引用全局 primes 变量（它不是固定的）来解决这个问题。
- 我避免在函数中使用
z 作为变量，因为这通常是不好的做法，因为 z 在函数中更常用作 default/implicit 第三个输入变量。
按照您的逻辑，不需要全局 primes 变量的更传统的迭代方法是：
q){$[not 0 in y mod/:x;x,y;x]}/[2;3 + til 100-2]
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
这使用 over (/) 进行迭代。
这仍然不是获得素数的最佳方式，因为这可能是最佳方式：https://github.com/KxSystems/kdb/blob/master/greplin.q#L6
q)p:{$[x<4;enlist 2;r,1_where not any x#'not til each r:p ceiling sqrt x]}
q)p 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
求素数的方法那么多，难敌Eratosthenes’ sieve，避免了mod.
等算术运算
下面，函数 es 将筛选函数 s 作为其第一个参数，将数字 N 作为第二个参数以查找下面的素数。
筛子的参数是一对：已知素数的列表，以及在 til N 中标记尚未消除的整数的布尔向量。它只是找到下一个未消除的数字并消除它的倍数。
sieve:{n:1+y?1b;(x,n;y and count[y]#10b where(n-1),1)}.
作为一元应用，可与While iterator/一起使用。
为了应用筛子，我们给它一个初始状态 (2;0b,1_N#10b) 并在 sqrt N 以下没有剩下的素数要测试时停止。结果就是找到的素数，non-multiples:{x,1+where y}.将它们组合起来。
es:{[s;N]{x,1+where y}. ({any z#y}[;;"j"$sqrt N].)s/ (2;0b,1_N#10b)}
这比已接受的答案中的 p 函数快一点并且 memory-hungry 少很多：
q)X:2000000
q)p:{$[x<4;enlist 2;r,1_where not any x#'not til each r:p ceiling sqrt x]}
q)(p X)~es[sieve]X
1b
q)\ts:10 p 2000000
726 471865536
q)\ts:10 es[sieve] 2000000
399 8391296
Finding primes with q 的第 1 部分讨论了这些和其他用于查找素数的函数算法。
所以我正在尝试创建一个函数来查找低于某个数字的所有质数。
这是我编写的代码，它不起作用，但可以帮助我解释我是如何尝试解决它的。我稍后会修复 0,1,2 的手动检查。
primes: enlist 2
g: h[;primes]
g'[3 + til 100-2]
h:{[x;y] z: x mod/: y; bool:(0 in z)=0b; if[bool; `primes set primes,x ]; }
所以我想做的是，对 3+ til 100-2 中的每个元素使用每个 (') 运算符来 运行 这个函数 h。但是，我希望它继续使用 primes 变量，而不是以 each 的方式。如果 z 中没有 0，则 if 语句将执行，因为这意味着 x 是质数。然后在 if 语句中，我想将 x 加入素数列表。
循环 1：x:3 y: enlist 2
在 if 语句中，它将 3 连接到 primes
循环 2：x:4 y: 2 3
if 语句不会执行
循环 3：x:5 y: 2 3
在 if 语句中，它将 5 连接到 primes
循环 4：x:6 y: 2 3 5
if 语句不会执行
感谢您的帮助！
您的逻辑可行，可以稍微整理一下：
q)primes:enlist 2
q)h:{m:x mod/:primes;bool:(0 in m)=0b;if[bool;`primes set primes,x];}
q)h'[3 + til 100-2];
q)primes
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
与您的一些不同之处：
- 如果您使用输入
primes投影h，例如g:h[;primes]那么primes输入在那个时间点是固定的，每次迭代都不会改变。所以你的函数中的y总是固定在2.
在这个例子中，我通过简单地引用全局 primes 变量（它不是固定的）来解决这个问题。
- 我避免在函数中使用
z作为变量，因为这通常是不好的做法，因为z在函数中更常用作 default/implicit 第三个输入变量。
按照您的逻辑，不需要全局 primes 变量的更传统的迭代方法是：
q){$[not 0 in y mod/:x;x,y;x]}/[2;3 + til 100-2]
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
这使用 over (/) 进行迭代。
这仍然不是获得素数的最佳方式，因为这可能是最佳方式：https://github.com/KxSystems/kdb/blob/master/greplin.q#L6
q)p:{$[x<4;enlist 2;r,1_where not any x#'not til each r:p ceiling sqrt x]}
q)p 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
求素数的方法那么多，难敌Eratosthenes’ sieve，避免了mod.
下面，函数 es 将筛选函数 s 作为其第一个参数，将数字 N 作为第二个参数以查找下面的素数。
筛子的参数是一对：已知素数的列表，以及在 til N 中标记尚未消除的整数的布尔向量。它只是找到下一个未消除的数字并消除它的倍数。
sieve:{n:1+y?1b;(x,n;y and count[y]#10b where(n-1),1)}.
作为一元应用，可与While iterator/一起使用。
为了应用筛子，我们给它一个初始状态 (2;0b,1_N#10b) 并在 sqrt N 以下没有剩下的素数要测试时停止。结果就是找到的素数，non-multiples:{x,1+where y}.将它们组合起来。
es:{[s;N]{x,1+where y}. ({any z#y}[;;"j"$sqrt N].)s/ (2;0b,1_N#10b)}
这比已接受的答案中的 p 函数快一点并且 memory-hungry 少很多：
q)X:2000000
q)p:{$[x<4;enlist 2;r,1_where not any x#'not til each r:p ceiling sqrt x]}
q)(p X)~es[sieve]X
1b
q)\ts:10 p 2000000
726 471865536
q)\ts:10 es[sieve] 2000000
399 8391296
Finding primes with q 的第 1 部分讨论了这些和其他用于查找素数的函数算法。