标签归档：编程

　　如果n与m是整数，那么m^n就是求m的n此方，即把m连乘n次！ 　　用算法描述起来很简单！在n次循环内不断自乘m，或者递归调用n次乘法即可，但是这极其没有效率！ 　　其实，可以将指数运算分解。注意到x^4可以由x^2自乘得到。 　　思路：当求m的n次方时，n可能是2k(偶数),可能是2k+1（奇数）,可能是0(不需要乘）.那么在计算m^n时，可以分成3部分进行递归。第一部分：n为0，不用计算。第2部分：n是偶数,递归计算m的n/2次方。第三部分：n是奇数，即表示为n=2k+1，那么递归调用计算m的n/2次方，再自乘m即可。

　　根据算数基本定理，任何一个整数n>1都可以表示为素数的乘积，切在不考虑顺序的情况下，该表达式是唯一的！即n=p1·p2·····pn。 　　写一个程序，读入一个正整数，把它的所有质因子找出来。例如，输入是72，72=2³·3²。质因数有2和3，为方便起见，将输出写成因数(指数)的形式！如输入72，则输出为2(3)3(2)。 　　思路：用质数依次去除n，从2开始一直到除不尽为止。如果除了i次，那么有2(i)。同样的道理3，5，7，···也按同样的办法处理！每一次除不尽时的余数，作为下次的被除数！ 　　代码如下：

　　在用“筛法”求素数时，每次筛除素数的动作，其实有很多是重复的！比如，如果一个数是3*5*7*9，那么删除的时候，它会被作为3的倍数，5的倍数，7的倍数，9的倍数，被重复判断删除4次。类似的，较大的数有较多的因数，那么，删除它所耗费的时间会很多！如何来优化“筛法”的算法，使之不重复呢？ 　　思路如下：从2开始，先删除2²，2³，2³，···，接着删除2·3，2²·3，2³·3，···，而此时并不删除3。再删除2·5，2²·5，2³·5，···，接下来2·7，2²·7，2³·7，···。一般而言，当发现p是一个素数时，先删除p²，p³，p³，···这一系列合数。因为p是素数，所以p²，p³，p³，···不可能被其它数整除。接着，找出比p大，但是第一个没有被删除的数q。再删除p·q，p²·q，p³·q，···。因为p是素数，q为目前为止未删除。所以p^¡·q之前也没有被删除。

　　如果整数 n ≠ 0，±1。如果除了显然因数 ±1 和 ±n 以外，n没有其他因数，那么 n 叫做素数。如：2，3，5，7是素数，4，6，10，15是合数。 　　根据素数的性质，有这样的定理：1、设 n 是一个正合数，p 是 n 的一个大于1的最小正因数，则 p 一定是素数。2、设 n 是一个正整数，如果对所有的素数 p ≤ √n，都有 p 不整除 n，则 n 一定是素数。 　　根据两条定理，可以得到寻找素数的群定性方法，通常叫做 埃拉托斯散筛法。 　　筛法具体描述如下：对于任意给定的整数 N ，要求出所有不超过 N 的素数。列出 N 个整数，从中删除小于等于√n的所有素数p1, …, pk的倍数。然后依次删除余下的整数（不包括1）就是所要求的不超过 N … 继续阅读 →

　　假设有一个数组x[]，它有n个元素，每一个都大于零，称x[0]+x[1]+…+x[i]为前置和(Prefix_Sum)，而x[j]+x[j-1]+…+x[n-1]为后置和(Suffix_Sum)。写一个程序，求出数组x[]中有多少组相同的前置和与后置和！ 　　如果x[]的元素是3,6,2,1,4,5,2，于是x[]的前置和有以下7个，即3,9,11,12,16,21,23，而后置和有2,7,11,12,14,20,23;于是11,12与23这3对就是值相同的前置和与后置和，因为：11=3+6+2=2+5+4, 12=3+6+1=2+5+4+1。而23是整个数组的和，所以前置和与后置和相同。