已不知在此吧潜水多久，出来发个帖。
之前连发三次都被度娘删了，没办法一楼只能喂度娘了。

众所周知，计算机最早被用于进行数学计算。然而最初的计算机只支持机器语言，导致许多人对此望而却步。直到各种编程语言诞生，编程的门槛才降低了许多。
个人看来，Scratch比较适合建立图形界面（真心比其他语言要方便），数值计算相对较弱，但使用其变量和列表，还是可以完成很多计算任务的。
本人打算以一个菜的不行总是被虐的信竞选手的身份，用Scratch 2实现一些算法、实际问题和（可能）数据结构，稍微更一些就回去潜水，本人学业繁忙，并没有太多时间。希望这些算法能在各位需要进行数值计算时发挥作用。

零、算法基础
不同的算法，其效率和适用范围有着很大的不同。当我们分析一个算法的运行时间时，我们通常采用时间复杂度这一概念来表示该算法的运行效率。
简单的说，我们只需要将程序中的总计算次数用关于问题规模的数学式子来表示，忽略其各项前的常数，选取其中增长速度最快的项（注意可能不止一个），置于大O记号之后，即是其时间复杂度。
下面举两个简单的例子来说明时间复杂度的计算。

例子一中，我们先用一次计算为a赋初值，接下来执行n次计算，所以时间复杂度为O(n)。

例子二中，先用一次计算赋初值，再进行n次计算。重点是下面的两重循环。
最里层的循环用了floor(n/2)次计算（floor即向下取整），可大致看做n/2次计算，于是外层循环中每次进行(n/2+1)次计算，于是一共进行了n(n/2+1)次计算，展开，为n^2/2+n，n^2/2这一项的增长速度较快，于是时间复杂度为O(n^2)。

一、数学、数论基础
估计这应该是此贴中与Scratch应用最多的内容了。
之前看到吧里一些个人看来比较弱的质数算法，打算写一下更高效的质数算法。（在C++中非常快，1秒能把1-10 000 000范围内的质数全计算出来，不知Scratch的表现如何）
在此之前，先说一些其他内容。

求幂问题
已知a和正整数b，求a^b。
一个很简单的方法，就是根据幂的定义直接计算。代码如下。

其时间复杂度显然为O(n)。
现在来思考一种更快的做法。
如何求2^10？
我们可以先求出2^5，再将其平方。
如何求2^5？
我们可以先求出2^2，将其平方再乘以2。
如何求2^2？
2乘以2就是了。
全过程只进行了4次乘法计算，比前一种方式的9次要少的多。当数据规模增大时，这一优势会逐渐增大。
用lg n来表示log 2 n（这在分析算法的复杂度时经常出现），则其时间复杂度为O(lg n)，这比O(n)要好得多。当n=1 000 000时，lg n约为20。
但这种算法需要用到递归，而Scratch实现递归较为麻烦，且递归会稍微慢一些，因此我们需要换一种思考方式。
当b为偶数时，a^b可化为(a^2)^(b/2)，而当b为奇数时，a^b可化为a^(b-1)*a，即 (a^2)^((b-1)/2)*a。这样，我们就避免了递归，用循环来实现这个被称为快速幂的算法。
代码如下。

最大公约数、最小公倍数
已知两个正整数a、b，求其最大公约数与最小公倍数。
分解质因数并不是一个好办法——难以实现，而且接下来会提到一种更有效的算法来解决这一问题。
学奥数的同学们可能知道，有一种称为辗转相除法的方法可以求出两数的最大公约数。在此之前先提一下模运算。
a mod b称为“a对于b取余”（应该是），其原理与除法类似。
7/3=2……1，于是7 mod 3=1。
我们只关心其余数。
用gcd(a,b)表示a与b的最大公约数，lcm(a,b)表示a与b的最小公倍数，
有gcd(a,b)*lcm(a,b)=a*b，所以，只要能快速求出gcd(a,b)，就能快速求出lcm(a,b)。
辗转相除法即欧几里得算法，被认为是世界上最早的算法，用上面定义的符号来表示如下：
gcd(a,0)=gcd(0,a)=a , gcd(a,b)=gcd(b,a mod b) (b≠0)
实现的时间复杂度为O(lg n)，别问我怎么证明，我也不会。
这里仅给出gcd的实现。

判断质数
已知一个正整数n，判断其是否是质数。
简单做法：从2到(n-1)循环，能整除就不是质数。
这个实在太蠢了，我就不写实现了。
如果n为合数，则令n=a*b(a>1,a,b为正整数，a≤b)，当a<b时，循环到b可以判断其不为质数，但事实上循环到a的时候即能作出同样判断。当a=b时，刚好能判断其不为质数。
所以，只从2到√n循环也能正确判断。这样，我们就将O(n)的时间复杂度降为O(√n)。
实际上，还有一种称为素性测试的算法，可以达到更低的时间复杂度，但不保证结果一定正确，在此不表。
O(√n)代码如下：

质数表
设计一种算法，支持查询操作，查询1-n之间的一个数是否为质数。
刺稽的东西来了，这是本章最后一块内容。
先上一种naive的做法：一个一个用刚才的质数算法试。O(n√n)。
如果有大量重复的查询，上面那种就会极其没用。
小改进：事先算出范围内的所有质数，存入表中，然后用Scratch的功能查找。
事实上，有一种叫做二分查找的算法，对于一个有序序列可以做到O(lg n)而不是O(n)查找，但不知道Scratch的“List”究竟是链表还是数组，如果是链表，那还是用功能块O(n)查找吧。
这就是吧里曾经的质数表算法，生成1-n的质数。可惜还有更高效的算法。
又是一个小改进：如果一个数能被a*b(a、b为正整数)整除，则其一定能被a和b分别整除。于是，我们可以只用质数去除要判断是否为质数的数，根据从1-n的循环顺序，我们会发现 1-√待判断数 的质数已经被算出来了，所以我们可以直接利用算出的质数表来进行判断。
别问我时间复杂度多少，我也不知道。渣机测试1-500 000可以9.54秒出结果。 （运行时不刷新屏幕！）
送上代码：

抱歉，上面的代码错了。
修改：（300 000可以29.19秒）

从一个一个循环的角度显然难以得到更优的解法了，接下来换一个角度，从筛法的角度来解决这一问题。

难道我是第一个顶贴的

我等着看开n次方