Xun’s blog

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

int euler4()
{
       int max=0;
       for(int i=999;i>99;i–)
           for(int j=999;j>99;j–)
         {
             int n=i*j;
             int a6=n/100000;
             int a5=(n/10000)%10;
             int a4=(n/1000)%10;
             int a3=(n/100)%10;
             int a2=(n/10)%10;
             int a1=n%10;
             if(a6==a1&&a5==a2&&a4==a3)
             {
                 if(n>max)
                     max=n;
             }
        }    
         return max;
}

 

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

int euler5()
{
     int n=20;   
     while(true)
     {
     bool flag=true;
     for(int i=2;i<21;i+=1)
     {
         if(n%i!=0)
         {
             flag=false;
             break;
         }
     }
     if(flag)return n;
     n++;
     }    
}

Problem 6

14 December 2001

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

int euler6()
{
     int n1=0,n2=0;
        for(int i=1;i<=100;i++)
        {
            n1+=i;
            n2+=i*i;
        }
        return n1*n1-n2;
}

Project Euler的第三题。

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

当时马上写下的代码是

_int64 euler3(_int64  n)
{
    for(_int64 i=n-1;i>1;i–)
    {
        if(IsPrime(i))
            if(n%i==0) 
               return i; 
    }
    return 1;
}

inline bool IsPrime(_int64 num)
{
    for(_int64 i=2;i<num;i++) {
        if(num%i==0) {
            return false;
        }
    }
    return true;
}

结果程序在我1.86G双核CPU上跑了20多个小时未果，汗一个。

仔细数了一下600851475143的位数发现是个千亿级的数字，而我用这个N^2复杂度加大量取模运算的算法显然是力不从心。

因为之前学过一点数论，突然意识到这个问题其实就是经典的大数分解问题。手边正好有一本Schneier的应用密码学，于是复习了一点数论知识。

因子分解目前最新的算法是数域筛选法，而分解110位以内的十进制数最快的方法是二次筛选法，而且二次筛选法相对要简单很多。

开始之前，首先要对素数怀有一种崇敬的心情，因为它不仅是RSA加密算法的基础，也是整个数学的基础，所有的数都可以表示为一些素数的乘积形式，而且这种表示是唯一的，那些只能表示成1乘以自身的数才是素数。

费马的方法

要分解N，如果能找到a，b使得a^2-b^2=N，那么N就能分解成（a-b)(a+b)，于是问题就转化成测试不同的a，使得a^2-N等于某数的平方。

a可以从sqrt（N）开始取，然后不停的加一，直到找到某个a^2-N=S^2。费马的方法之所以可行是因为a^2-N相对于N来说是一个很小的数（至少在开始的时候）。

这种方法的缺点是在碰到S^2之前要测试很多a^2-N，因为平方数不那么容易碰到。一种改进是把得到的a^2-N序列中的数相乘，看能不能更快的得到一个平方数。因为如果

（a1^2-N）（a2^2-N）=S^2，设A=a1*a2

A^2-S^2=N(N-a1^2-a2^2)=(A-S)(A+S)

这样(A-S)和(A+S)中必有一个同N有公因子，然后就可以用欧几里德算法很快得找出这个因子。

a^2-N序列中的数相乘很容易得到一个非常大的数，这好像会带来很大的运算量，但这种方法可行是因为有一种方法可以快速的判断多个数相乘后的结果是否为平方。

因为任何数都有一种唯一的素因子分解形式，一个数是否为平方，取决于它的素因子能否等分为两份，即所有的素因子的指数为偶数。据此我们可以以素数为列，根据每个数的素因子存在情况建立矩阵，不存在或指数为偶数的取零，指数为奇数的取一（因为我们只需要判断两个数相乘，也就是矩阵的行相加后各素数指数的奇偶性），这会涉及到对这些书的素数分解，但因为他们相对于最终要分解的数很小，难度也会小很多。但是要注意挑那些最大素因子比较小的数，这样可以控制矩阵列数的大小。对于最大素因子有一种叫B-smooth提法，也就是说最大素因子不大于B的数都是B-smooth的。

事实上随着需分解的数增大，这个算法的瓶颈在于从a^2-N序列中找出素因子小的数。这时候会用到数论中的二次剩余理论来筛选出这些数，这也是这个算法的命名由来。

二次剩余的定义：如果存在a使得a^2-N=kp（p是素数）则N是模p二次剩余。

注意到需要筛选数列正是计算a^2-N得到的，因此如果N不是模p二次剩余，p就不会是这个序列中的数的因子，（否则（a^2-N）%p=0）。

而判断N是否是模p剩余有一个快速的方法：计算N^(p-1)/2 % p 是否等于1。

于是我们可以设定一个阀值素数P，然后找出所有小于P并使N二次剩余的素数，用这些素数和他们的幂次方去除a^2-N序列，最后序列中等于1的那些数就都是P-smooth的了，用这些筛选出的P-smooth的数和小于P并使N二次剩余的素数序列构建平方判断矩阵，来寻找相乘造成平方的数的运算量就大大降低了。

编程的时候发现对于千亿级别的数，费马的方法就可以轻松解决了。

/*判断n是否是平方*/

bool quad(_int64 n)
{
    _int64 sqr=sqrt(double(n));
    if(sqr*sqr==n)
        return true;
    else return false;
}

/*素数判断是一个很大的话题，这里用的是最野蛮的方法*/

bool IsPrime(_int64 num)
{
    for(_int64 i=2;i<num;i++) {
        if(num%i==0) {
            return false;
        }
    }
    return true;
}

_int64 fermat(_int64 n)
{
    _int64 fac1,fac2,s;
    _int64 a=sqrt(double(n))+1;
    while(true)
    {
        s=pow(double(a),2)-n;
        if(quad(_int64(s)))
        {
            fac1=a-sqrt(double(s));
            fac2=a+sqrt(double(s));
            if(IsPrime(fac1))
            {
                cout<<"The factor is "<<fac1<<endl;
                return n;
            }
            else
            {
                fermat(fac1);
            }
            if(IsPrime(fac2))
            {
                cout<<"The factor is "<<fac2<<endl;
                return n;
            }
            else
            {
                fermat(fac2);
            }               
        }
        a++;
    }

在main函数里用time计了一下时，一共用了十秒，于是草草收工。

http://blogs.msdn.com/devdev/archive/2006/06/19/637332.aspx
http://en.wikipedia.org/wiki/Quadratic_sieve
http://www.boo.net/~jasonp/qs.html

显然这不是一个创造欧拉的工程，做做题而已，一想到欧拉几百年前就懂了我现在还不明白的东西就比较汗颜。

http://projecteuler.net

第一题

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

static int  Euler(int max)
{
    int mul5 = (max - 1) / 5;
    int mul3 = (max - 1) / 3;
    int mul15 = (max - 1) / 15;
    int sum=0;
    sum =  (1 + mul5)*mul5 / 2 * 5;
    sum += (1 + mul3)*mul3 / 2 * 3;
    sum -= (1 + mul15)*mul15 / 2 * 15;
     return sum;
}

第二题

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

static int  Euler(int max)
{
    int i = 1, j = 2, sum = 2, count = 0, tem = 0;
    while (j <= max)
    {
        tem = i;
         i = j;
        j = tem + j;
        count += 1;
        if (count == 3)
        {
            sum += j;
            count = 0;
        }
    }
    return sum; 
}

只有奇数加奇数才能得到偶数，所以偶数的出现稳定在3次一个循环，引入count来避免使用偶数判断运算。

Linux下的输入法有一个XIM框架，X程序通过XIM协议与输入法联系。如用户按下键盘按键后不直接把字符传给X程序，而是输入法程序，输入法处理后再传给X程序。aptitude install scim-pinyin同时安装了scim平台和拼音输入法。接下来就是启动scim和通知x程序使用scim。把这些事情放在一个脚本里面就是：

/usr/bin/scim -d
export  XMODIFIERS=”@im=SCIM”
export GTK_IM_MODULE=scim

XMODIFIERS是X程序用来识别输入法的标记，GTK和QT也有单独的一套。

为了开机自动运行把这个脚本保存为~/.xinput，然后再~/.xinitrc中加一句source ~/.xinput。

如果输入法工作不正常，检查一下

ps aux|grep scim                         scim是否启动。
export |grep XMODIFIERS        XMODIFIERS变量是否正确设置。
locale                                           LC_CTYPE是否设为zh_CN.UTF-8

http://www.scim-im.org/projects/imengines
http://code.google.com/p/ibus/wiki/PinYinUserGuideCN
http://sourceforge.net/projects/novel-pinyin/
http://www.opensolaris.org/os/project/input-method/

X的启动方法几种
最直接的是运行xinit或xinit firefox，不带参数的话会默认打开一个term，进入这样的X能做的事情很有限（窗口不能移动会互相覆盖），但可以让我们对窗口管理器有一个感性的认识。

startx
在装了某个窗口管理器（如openbox或fluxbox）后，可以用startx命令进入一个带窗口管理功能的X界面。startx是一个在/usr/bin目录下的脚本，它会分别读取用户级和系统级的一些配置，然后用xinit运行X。配置文件有xinitrc，xserverrc，xsession等，一般系统级的配置在/etc/X11目录下，而用户级配置在用户主目录并用.xinitrc的形式命名，原则是用户级配置覆盖系统级配置。
如果系统安装了多个窗口管理器可用startx -m openbox的形式指定，或者在.xinitrc中加一句exec openbox。否则startx会调用/usr/bin/x-window-manager启动默认窗口管理器，它是一个指向/etc/alternatives/x-window-manager的链接，而后者是一个指向真正窗口管理器如/usr/bin/openbox的链接。这个链接通过update-alternative –config x-window-manager维护，但update-alternative是怎样知道系统有多少个窗口管理器呢。
在Debian下用strace -eopen update-alternatives –config x-window-manager监控update-alternatives的文件操作，可以发现它打开了/var/lib/dpkg/alternatives/x-window-manager，这是一个记录了系统安装的窗口管理器的文本文件，估计用Apt安装的窗口管理器都会来这里登记一下。

关于update-alternatives
因为Linux有很多相同功能的软件，alternatives是一个用来统一这些软件的机制，比如我想开一个浏览器只需要运行x-www-browser而不用管系统是装了Firefox还是Opera，alternatives机制会帮我们选择一个可用的。具体实现是在/etc/alternatives/目录创建一些通用的链接，并根据情况指向真实的程序，update-alternatives是Debian用来维护/etc/alternatives/目录下那些链接的Perl程序。如update-alternatives –config x-window-manager用来更新/etc/alternatives/x-window-manager这个链接。

或者还可以安装启动管理器。

启动管理器是一个管理登录的程序，如GNOME用的gdm和KDE用的kdm。用这种方法的话就不需要用户手动输入命令，而是像Windows一样开机后直接得到一个输入帐号密码的登录界面。gdm们获取自动运行机会的方法是把自己加到开机默认运行级别的rc*.d目录。

在VBox窗口的Devices， mount CD， CD image然后选中VBoxGuestAdditions.iso确定。

Debian控制台下：
mkdir /mnt/cd
mount /dev/cdrom /mnt/cd -t iso9660
cd /dev/cdrom
sh VBoxLinuxAdditions-x86.run help
sh VBoxLinuxAdditions-x86.run

之前要安装build-essential和Linux-header文件
aptitude install build-essential
uname -r查看内核版本。
aptitude search linux-header。
安装对应的头文件。

GuestAdditions的一些功能：

1. 鼠标指针无缝连接，无需按右Ctrl切换。
2. 更好的显示支持，在用户缩放Vbox窗口的时候自动调整Guest的分辨率来配合缩放。
3. 共享文件夹。
4. 共享剪切板。
5. 以及非常酷的无缝窗口。

共享文件夹访问
net use x: file:///P|/vboxsvr/sharename
mount -t vboxsf sharename /mnt/vb

无缝窗口把程序窗口从虚拟机里分离出来，这样可以把两个系统中的程序窗口统一起来，貌似Wine的完美替换，右Ctrl+L呼出。

另外装上GuestAdditions以后，就不能以Framebuffer方式启动Linux，否则会僵死掉，至少在我的机器上是这样。

图形界面下面的Linux更易于理解也更接近Linux的本质，而且基本上大部分的事情在startx之前就可以完成了。

控制台下的图像处理如mplayer和fb开头的软件都依赖framebuffer，framebuffer是Linux对显示设备的抽象，设备符号一般为/dev/fb0，可以把它理解为一幅显示到屏幕的图像，用户只要修改这幅图像就能修改显示器的视频显示，比如用dd if=/dev/fb0 of=fb.raw就可以截屏，只是因为生成的是raw图像数据，无法用图像浏览软件直接打开，还需用fbgrab等软件处理一下。而 dd if=fb.raw of=/dev/fb0则可以把之前保存的图像写回显示屏。
Debian默认支持framebuffer，但须手动开启，方法是编辑/boot/grub/menu.lst在kernel那行加上vga=ask或0×343，具体值的设置可先用hwinfo –framebuffer确定。

控制台下的软件：
ftp:lftp
http下载：wget
浏览器：lynx
图片浏览：fbi
截屏：fbgrab
编辑：vi
文件管理：mc
影音：mplayer -vo fbdev
鼠标支持：gpm

lynx
export WWW_HOME=www.google.com设置主页。
方向键操作，d下载选中文件。a书签。g跳转。k显示命令列表。

wget
export http_proxy=”http://proxy.com:8080″设置代理。
wget -r -l2 –accept=bz2,gz http://cross-lfs.org/view/clfs-sysroot/arm/materials/packages.html 下载指定页面两层链接内的所有bz2和gz文件。
wget -rkpN -np -t 5 -T 20 URL 抓全站。

lftp
get ，put， mirror，mirror -r，bookmark。

vi
i,a,o,O进入编辑模式。
r修改一个字符后返回Normal模式，R进入修改模式。
x删除一个字符。
dd删除行。
yyp复制行。

http://www.linuxsir.org/bbs/thread245239.html
http://www.linuxsir.org/bbs/thread199931.html
http://fbsplash.berlios.de/wiki/doku.php

因为当时X还没有开启，控制台不可能用X核心字体或者xft，而是有自己的一套，一般放在/usr/share/consolefonts下。可以用aptitude install console-terminus安装专门为其准备的console-terminus字体，这是一套适合控制台使用很漂亮的等宽字体。

在使用之前，用unicode_start打开Unicode模式。
whereis unicode_start
vi unicode_start

db_mode -u
dumpkeys | loadkeys –unicode
consolechars –font= –sfm=
echo -n -e ‘33%G’

这个脚本先把键盘置于Unicode模式，然后用consolechars工具接受我们传来的参数设置字体，最后用echo -n -e ‘33%G’命令把控制台置为Unicode模式。

自己设置字体的话，先ls /usr/share/consolefonts浏览字体。
consolechars -f Uni3-TerminusBoldVGA16查看效果。
确定了以后在/etc/console-tools/config中修改SCREEN_FONT为自己指定的字体。
如SCREEN_FONT=Uni3-TerminusBoldVGA16.psf

控制台只能使用这种psf字体，而系统提供的包括安装的Terminus字体中都没有中文字符，所以有Unicode编码的中文名文件时用ls命令查看会是一些小方框。

所以如果想让控制台支持中文显示以及输入，还需要其他更麻烦的步骤，如安装zhcon，然后用zhcon –utf8开启一个新的支持中文的控制台，那样刚才针对fb设置的字体都会无效。
也可以安装unicon，unicon通过修改内核提供中文支持，需要重新编译内核。另外还有fbiterm, jfbterm等。

以繁體中文介面安裝 Debian 時預設會安裝的套件

http://www.turbolinux.com.cn/products/tlw/tlc/node143.html

http://tetralet.luna.com.tw/index.php?op=ViewArticle&articleId=194&blogId=1