如何判断一个数是否是素数

發表於 2014-03-31

这个问题对于学习编程的人来说不陌生，但并没有想象中那么简单，这里面还是很深的。一般来说是用比这个数小的素数去除，如果都不能整除，则是素数。可是这种方法必须要求你知道比这个数小的所有素数，所以我觉得不是很实用。

去年找实习时，微软的面试官也问了我这题。刚开始只想到最基础的方法，假设需要判断的是n, 如果n是2则是素数，如果n是1或者是大于2的偶数，则是素数，如果n是大于2的奇数，则从2开始到 n的平方根，如果n可以被其中任何一个整除则这个数不是素数，否则是素数。

之后面试官问还有没有更好的方法，考虑之后，想到《C语言名题百则精选中曾提到过一种方法，对于大于等于6的数，都可以表示成6n,6n + 1,6n + 2, 6n + 3, 6n + 4, 6n + 5,其中只有6n + 1和6n + 5是素数，所以对于大于6的数，如果不能被2 ， 3 ， 5整除，则只需用6n + 1和6n + 5这些数去除。

最近在做欧拉工程第58题，我先生成一个很大的素数表，然后来判断是否是素数，可是这个题目中用到的素数实在是太大了，这种方法不实际。之后用了前面两种方法，也是不行，速度太慢了。最后上网找方法，找到了米勒-拉宾素性测试法，终于把问题解决了。难道说，当时的面试官是想问这种方法？
以下内容来自http://en.wikipedia.org/wiki/Miller-Rabin_primality_test 。这个方法需要用到费马小定理，x^2 = 1 (mod p)，费马这厮真是有趣，搞出几个定理都不给出证明，这个小定理还好，最要命的是那个大定理，耗费了几百年才被人给出证明。这里空白太少，写不下证明，只好直接拿来用了。

先给一个引理，当p是素数,若x^2 = 1 (mod p),则x = 1(mod p)或者 x = -1(mod p),这个引理的证明很简单，由x ^ 2 = 1 (mod p)得(x + 1)(x – 1) = 0 （mod p)，而由于p是素数，所以x + 1 = 0 (mod p)或者x – 1 = 0 (mod p).

现在设n是一个素数且n > 2,则 n – 1一定是偶数，并且可以表示成2 ^s d的形式，其中s和d都为正整数，且d是奇数。那么对于任意2 <= a < n,
a^d = 1 (mod n)或者a^(2^r d) = - 1(mod n),其中0 <= r <= s – 1。

证明如下：
由费马小定理可知，当n是素数时
a^(n – 1) = 1 (mod n), 我们将n – 1表示成2^s d,再由上面的引理得，如果我们对n – 1进行开方，则可以得到a^(2^(s – 1) d)=1 (mod n)或者a^(2^(s-1) *d) = -1 (mod n),如果是后者，则已经满足了，如果是前者，则继续这个开方过程，如果我们一直都是得到1，最终就是
a^d = 1(mod n).

而米勒-拉宾测试法就是用了这个定理的逆否命题。也就是，如果 a^d != 1 (mod n)且a^(2^r *d) != -1 (mod n)对于所有的0<=r<=s-1,则n不是素数。

联系作者

欧拉工程-问题60

By robinjia

發表於 2014-03-30

原题链接http://projecteuler.net/problem=60

Prime pair sets

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

素数对集合

素数3，7，109和673非常有特色。取其中任意两个素数，以任意顺序链接起来都是素数。例如，取7和109，7109和1097都是素数。这四个素数的和792，代表着具有这种特征的四素数集中的最小和。

求具有取其中任意两个素数，连接起来都是素数的五素数集的最小和。

解答：

依然是暴力解决。唯一需要注意的是，判断素数的方法必须使用米勒-拉宾素性测试方法，否则速度无法接受。

联系作者

欧拉工程-问题59

By robinjia

發表於 2014-03-29

原题链接http://projecteuler.net/problem=59

XOR decryption

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both “halves”, it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher1.txt (right click and ‘Save Link/Target As…’), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

异或加密
在计算机中的每个字符都被分配一个唯一的码值，最常用的标准是ASCII（美国标准信息交换码).例如，大写的A = 65，星号(*) = 42,小写的k = 107.

有一种现代的加密方法是将文本文件转化成对应的ASCII,然后将每一个字节与密码中的一个值异或。使用异或方法加密的一个优点是，在密文中使用同样的密钥可以得到明文。例如, 65 XOR 42 = 107 , 之后 107 XOR 42 = 65.

对于不可破解的加密，密钥的长度与明文一样长，并且密钥由随机的字节组成。一个用户将密文和密钥保存在不同的地方，如果没有同时拿到密文和密钥，将不可能破解信息。

不幸的是，这种方法对于许多用户都不实际，因此一个改良的方法是使用密码作为密钥。如果密码的长度小于信息，这也是最常见的情况，那么密钥就要循环贯穿信息。综合考虑，这种方法为了保证安全，选择一个足够长的密钥，为了便于记忆，也必须足够短。

你的任务已经简化了，因为密钥是由三个小写字母构成。使用cipher1.txt（右击，链接另存为），这是一个经过加密的ASCLL码，已经知道的是明文是由英文单词构成，请解密信息，并求原始信息中ASCLL码的总和.

解答：
暴力破解，用常见的英文单词the来判断。

联系作者

crontab定时运行脚本

By robinjia

發表於 2014-03-25

在Linux上经常需要定时运行某个脚本，这是crontab就派上用场了。对于如何使用crontab,一般google。事实上，我一直很好奇的是，网上那些人关于crontab的知识到底从哪里得来的，知道man crontab后我才知道，原来他们也是看的手册。
man crontab后，没有关于如何编写crontab任务的说明，看到see also crontab(5)后,执行man 5 crontab,发现这里有说明如何编写crontab任务。这样以后就不需要遇到一个问题，就上网找，直接看手册就好了。

一般说来，都是仿照晚上的例子写，如这里http://www.blogjava.net/xiaomage234/archive/2007/12/26/170490.html后来才发现，给出的例子中有一个坑。

1	* /1 * * /usr/local/apache/bin/apachectl restart

每小时重启apache
这个例子中说每小时重启apache，试着写了之后，才发现每一分钟都会重启。仔细分析后才发现原因,因为第一列是分钟的位置,而使用*号，则代表0-59分钟，于是在一个小时里，0-59分钟都会重启apache,等到59分钟重启apache后，已经过了一小时，于是又回到0分钟，于是apache又重启了。

所以以后遇到位置的命令时，不要立马上网找，可以先看看手册的说明。或者找一个靠谱的网页看，后来才发现http://www.centos.bz/2011/03/auto-run-task-crontab/这里写的比较靠谱。在找这些命令使用过程中发现，网上这般人经常抄来抄去的，浪费别人的时间，太无聊了。

联系作者

在C++的sort排序中永远让比较函数对相等的值返回false

By robinjia

發表於 2014-03-24

很久之前，线上的程序跑着跑着，莫名其妙的就coredump了，找了很久都不知道原因。因为coredump的次数不是很多，有时好几天了也才dump了一次，所以也很难确定是在哪个地方出错了。通过版本回溯，慢慢缩小了出错的范围，可是我还是不知道在哪里出错了，直到今天晚上组长和我说了可能出错的地方，才知道原来有这么一个坑存在。

他说使用sort排序时，比较函数编写时，如果两个值相等返回true可能会存在问题，于是我看了自己写的，两个值相等时，正是返回true.

1
2
3

int cmp(const int &a, const int &b) {
    return a >= b;
}

可是我还是看不出这里有什么错误，google之后找到了解答,在一篇文章里说到，当排序的个数超过16个时，且这些书数全部相等时，如果比较函数在两个值相等返回true时就会出错。这是因为sort行数的实现中，当超过16个数时，使用快速排序，而且假定一定存在两个数不相等。具体可参看http://blog.sina.com.cn/s/blog_79d599dc01012m7l.html

联系作者

安装Maven

By robinjia

發表於 2014-03-08

很早之前，在写第一个Servlet时，一直配置不成功，写一个Hello World!都成问题，于是转而奔向PHP，最近由于工作需要，要重新拾起Java那套东西。因为是用Maven做的管理，于是要安装Maven，到网上找参考资料，竟没安装好，于是到官网找解答，最终找到。

安装Maven之前，已经假设你安装好JDK.有一点需要注意的是,Maven3.2要求JDK1.6及以上,Maven3.0/3.1则要求JDK1.5及以上，否则会出现版本错误

1.下载Maven

到官网http://maven.apache.org/下载Maven,当前最新稳定版本为3.2.1

对于Windows系统，下载Maven 3.2.1 (Binary zip)

2.解压Maven,配置环境变量

将Maven解压，这里假设放在d:\apache-maven-3.2.1

之后进行环境变量配置，

在系统变量中增加M2_HOME,值为d:\apache-maven-3.2.1

在系统变量中增加M2,值为%M2_HOME%\bin

如果已经存在用户变量Path，则在值的前面增加%M2%；注意一定要加上这个分号

如果不存在用户变量Path,则新建它，并赋值为%M2%

3.测试Maven

在命令行中执行mvn –version，在我的电脑上显示如下,

Apache Maven 3.2.1 (ea8b2b07643dbb1b84b6d16e1f08391b666bc1e9; 2014-02-15T01:37:5

2+08:00)

Maven home: d:\apache-maven-3.2.1

Java version: 1.6.0_15, vendor: Sun Microsystems Inc.

Java home: D:\Java\jdk1.6.0\jre

Default locale: zh_CN, platform encoding: GBK

OS name: “windows 7”, version: “6.1”, arch: “x86”, family: “windows”

如果不是这样，看看环境变量是否配置正确，以及JDK版本是否匹配

4.Eclipse的Maven插件安装

在插件安装上，网上的资料很多已经过时了，因为都是很早之前的链接。顺着官网找到了eclipse的Maven插件安装链接http://download.eclipse.org/technology/m2e/releases/

我用的是Eclipse Kepler.在Help->Install new software中，将以上安装链接加入，名字为Maven，之后即可下载插件

5.配置Maven插件

在Window->Preferences中,选择Maven

点击Installations,此时还是用插件自带的Maven版本3.0.4,而且Global settings是空的我们需要添加自己安装的版本，点击Add,打开D:\apache-maven-3.2.1即可，最终结果如下：

此时Maven插件将会使用安装的Maven3.2.1版本

之后点击User Settings,可以看到如下结果

这里也许最让你迷惑的是这三个概念，Global Settings, User Settings,以及Local Repository。因为我也未深入理解，所以也只能在这里说说我的理解。简单来说，

Global Settings就是一些全局设置，设置了中央jar仓库的位置等等.

User Settings设置了用户私有jar仓库的位置等等.

Local Repository是本地jar仓库的位置.

假设你现在在开发一个应用，它需要使用一个jar,则Maven会先到Local Repository中寻找，如果没找到这个jar,则它会到User Settings中设置的用户私有jar仓库中查找，如果还是没找到，则到Global Settings设置的中央jar仓库中查找，如果还是没找到，Maven将报错，指示jar未找到。

网上还有介绍另外一种方法，也就是先去下载Eclipse的Maven插件，之后再将插件导入到Eclipse, 只是因为直接用URL的方法已经解决了安装问题，所以没有尝试。

6.Hello World例子

之后用《Maven by Example》中的一个例子来介绍安装介绍。命令行进入Eclipse工作目录，我这里是d:\workspace,执行以下命令

mvn archetype:generate -DgroupId=org.sonatype.mavenbook -DartifactId=simple -Dpackage=org.sonatype.mavenbook -Dversion=1.0-SNAPSHOT

之后敲几次回车，一个最简单的HelloWorld项目就建立好了。

之后cd simple进入simple目录，如果你有兴趣，可以看看Maven生成的内容，

其目录结构如下

simple/

simple/pom.xml

simple/src/main

simple/src/main/java

simple/src/test

simple/src/test/java

其中src/main存放源文件,src/test存放测试文件,pom.xml为Maven提供编译信息，

执行mvn install，编译,测试，打包项目

执行java -cp target/simple-1.0-SNAPSHOT.jar org.sonatype.mavenbook.App

看到输出的 Hello World！

事实上，在命令行中，一个困惑是如何选择新建项目的类型，命令行里一共列出了九百多种，而很难知道哪个编号对应的是哪一种项目类型。

关于Maven的更多内容可以去sonatype官网下载《Maven by Example》,绝对值得一看。

参考文章：

http://www.blogjava.net/fancydeepin/archive/2012/07/13/eclipse_maven3_plugin.html

联系作者

用select实现精确定时器

By robinjia

發表於 2013-12-26

之前为了找出Sphinx中index ‘test1’: search error: query too complex, not enough stack (thread_stack=1217498K or higher required)这个bug,大致看了一下Sphinx的源码，发现问题的原因是在计算线程使用的空间时出错，具体原因依然没有找到，还在努力当中。在这个过程中，看到以下这段程序

void sphSleepMsec ( int iMsec )
{
    if ( iMsec<0 )
        return;

#if USE_WINDOWS
    Sleep ( iMsec );

#else
    struct timeval tvTimeout;
    tvTimeout.tv_sec = iMsec / 1000; // full seconds
    tvTimeout.tv_usec = ( iMsec % 1000 ) * 1000; // remainder is msec, so *1000 for usec

    select ( 0, NULL, NULL, NULL, &tvTimeout ); // FIXME? could handle EINTR
#endif
}

其实就是一个毫秒定时器，《UNIX环境编程》第14章的习题就要求实现一个这样的函数。看这段程序，又是令人恶心的匈牙利命名，把它改为正常点的比较好。程序中的注释”//FIXME?could handle EINR”说的是select会被SIGINT信号中断，那么这个定时器也会因为这个原因而被中断信号中断，看看能否提供不被中断的方法。立刻就想到了忽略中断信号，试了一下，其实还是挺容易的。难道这种直接忽略中断信号还是存在问题？

#include <sys/select.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
void sleep_ms(int msec) {//睡眠msec毫秒
    if (msec < 0)
        return;
    signal(SIGINT, SIG_IGN);
    struct timeval tv; 
    tv.tv_sec = msec / 1000;//除以1000，得到秒数
    tv.tv_usec = (msec % 1000) * 1000;//得到剩余的毫秒数，之后乘以1000得到微秒数
    select(0, NULL, NULL, NULL, &tv);
}
int main() {
    printf("start sleeping\n");
    sleep_ms(4000);
    printf("finish sleeping\n");
    return 0;
}

联系作者

用epoll提供telnet服务的代码(续)

By robinjia

發表於 2013-12-26

最终的代码如下，这里修正了对nc命令无法处理的问题

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <fcntl.h>
#include <arpa/inet.h>
#include <sys/epoll.h>
#include <stdlib.h>
#include <netinet/tcp.h> 
#include <ctype.h>
#include <assert.h>
#define MAX_EVENTS 10
#define PORT 9999
//从buf中得到命令
void _get_command(char *buf, char *cmd) {
    int i = 0;
    int j = 0;
    while (!isalpha(buf[i]))
        i++;
    while (buf[i] != '\0' && buf[i] != ' ' && buf[i] != '\r' && buf[i] != '\n') {
        cmd[j++] = buf[i];
        i++;
    }
    cmd[j] = '\0';
}
// 返回成功发送的字节数
int Send(int sock, void *buffer, int size)
{
    int nsend = 0, total = 0;
    int err;
    if(NULL == buffer || 0 == size) {
        return 0;
    }
    while(size > 0) {
        nsend = write(sock, (char*)buffer + total, size);
        if(nsend == -1) {
            err = errno;
            if(EINTR == err) {
                printf("send data to socket[%d], error is %s[%d]\n", 
                            sock, strerror(err), err);
            } else {
                printf("Fail to send data to socket[%d], error is %s[%d]", 
                            sock, strerror(err), err);
                return -1;    
            }
        } else {
            total += nsend;
            size -= nsend;
        }
    }
    return total;
}
//处理重置命令
void process_reset(int sock){
    char mess[] = "reset successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}
//处理错误命令
void process_error(int sock) {
    char error[] = "ERROR\r\n";
    Send(sock, error, strlen(error));
    return;
}
void process_stats(int sock){
    char mess[] = "stats successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}

//处理退出命令
void process_quit(int sock) {
    close(sock);
}

int process_command(int sock, char *buf) {
    assert(buf != NULL);

    /*char cmd[BUFSIZ];
    _get_command(buf, cmd);    
    printf("command: %s\n", cmd);

    if (strcmp("stats",cmd) == 0) {
        process_stats(sock);
    } else if (strcmp("reset", cmd) == 0) {
        process_reset(sock);
    } else if (strcmp("quit", cmd) == 0){
        process_quit(sock);
    } else {
        process_error(sock);
    }*/
    Send(sock, buf, strlen(buf));

    return 0;
}

//设置socket为非阻塞
void setnonblocking(int sockfd) {
    int opts;
    opts = fcntl(sockfd, F_GETFL);
    if (opts < 0) {
        perror("fcntl(F_GETFL)\n");
        exit(1);
    }
    opts = (opts | O_NONBLOCK);
    if (fcntl(sockfd, F_SETFL, opts) < 0) {
        perror("fcntl(F_SETFL)\n");
        exit(1);
    }
}
int main() {
    int listenfd, conn_sock, epfd;
    char buf[BUFSIZ];
    socklen_t clilen;
    struct sockaddr_in cliaddr, servaddr;
    struct epoll_event ev, events[MAX_EVENTS];
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd < 0) {
        printf("create socket error\n");
        return -1;
    }
    int on = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on));
    setnonblocking(listenfd);
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(PORT);

    if(bind(listenfd,(struct sockaddr*)&servaddr,sizeof(struct sockaddr))<0){
        printf("bind error\n");
        close(listenfd);
        return -1;
    }

    if(listen(listenfd, 5) < 0) {
        printf("listen error\n");
        close(listenfd);
        return -1; 
    }
    epfd = epoll_create(MAX_EVENTS); //生成epoll专用的文件描述符
    if (epfd == -1) {
        printf("epoll_create\n");
        return -1;
    }
    ev.events = EPOLLIN | EPOLLET; //设置处理的事件类型,设置为边沿触发
    ev.data.fd = listenfd;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, listenfd, &ev) == -1) {
        printf("epoll_ctl add listen_sock fail\n");
        close(listenfd);
        return -1;
    }
    while (1) {
        int timeout = 1000; 
        int nfds = epoll_wait(epfd, events, MAX_EVENTS, timeout);
        if (nfds == -1) {
            printf("epoll_wait\n");
            return -1;
        }
        for (int i = 0;i < nfds; ++i) {
            int fd = events[i].data.fd;
            if (fd == listenfd) { //监听事件
                while ((conn_sock = accept(listenfd, NULL, NULL)) > 0) {//循环处理accept,这样可以处理多个连接在就绪队列中的情况
                    printf("accept %d\n", conn_sock);
                    setnonblocking(conn_sock);
                    ev.events = EPOLLIN | EPOLLET; //设置为边沿触发
                    ev.data.fd = conn_sock;
                    if (epoll_ctl(epfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) {
                        printf("epoll_ctl: add fail\n");
                        close(conn_sock);
                        return -1;
                    }
                }
            } else if (events[i].events & EPOLLIN) {//读事件，说明有数据从客户端发来
                int n = 0;
                int nread = 0;
                while ((nread = read(fd, buf + n, BUFSIZ - n)) > 0) {
                    n += nread;
                }
                //printf("n %d nread %d\n", n, nread);
                if (nread == -1 && errno != EAGAIN) {//读数据错误,关闭描述符
                    printf("read error\n");
                    close(fd); //关闭一个描述符，它会从epoll描述符集合中自动删除
                    continue;
                }
                if( n > 0) {
                    process_command(fd, buf);
                    memset(buf, 0, sizeof(buf));
                }
                if(nread == 0) { //客户端关闭连接，关闭相应的描述符
                    close(fd);
                    continue;
                }
            }
        }
    }
}

联系作者

用epoll提供telnet服务的代码

By robinjia

發表於 2013-12-25

这是之前写的用epoll提供telnet服务的代码。

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <fcntl.h>
#include <arpa/inet.h>
#include <sys/epoll.h>
#include <stdlib.h>
#include <netinet/tcp.h> 
#include <ctype.h>
#include <assert.h>
#define MAX_EVENTS 10
#define PORT 9999
//从buf中得到命令
void _get_command(char *buf, char *cmd) {
    int i = 0;
    int j = 0;
    while (!isalpha(buf[i]))
        i++;
    while (buf[i] != '\0' && buf[i] != ' ' && buf[i] != '\r' && buf[i] != '\n') {
        cmd[j++] = buf[i];
        i++;
    }
    cmd[j] = '\0';
}
// 返回成功发送的字节数
int Send(int sock, void *buffer, int size)
{
    int nsend = 0, total = 0;
    int err;
    if(NULL == buffer || 0 == size) {
        return 0;
    }
    while(size > 0) {
        nsend = write(sock, (char*)buffer + total, size);
        if(nsend == -1) {
            err = errno;
            if(EINTR == err) {
                printf("send data to socket[%d], error is %s[%d]\n", 
                            sock, strerror(err), err);
            } else {
                printf("Fail to send data to socket[%d], error is %s[%d]", 
                            sock, strerror(err), err);
                return -1;    
            }
        } else {
            total += nsend;
            size -= nsend;
        }
    }
    return total;
}
//处理重置命令
void process_reset(int sock){
    char mess[] = "reset successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}
//处理错误命令
void process_error(int sock) {
    char error[] = "ERROR\r\n";
    Send(sock, error, strlen(error));
    return;
}
void process_stats(int sock){
    char mess[] = "stats successful\r\n";
    Send(sock, mess, strlen(mess));
    return;
}

//处理退出命令
void process_quit(int sock) {
    close(sock);
}

int process_command(int sock, char *buf) {
    assert(buf != NULL);

    /*char cmd[BUFSIZ];
    _get_command(buf, cmd);    
    printf("command: %s\n", cmd);

    if (strcmp("stats",cmd) == 0) {
        process_stats(sock);
    } else if (strcmp("reset", cmd) == 0) {
        process_reset(sock);
    } else if (strcmp("quit", cmd) == 0){
        process_quit(sock);
    } else {
        process_error(sock);
    }*/
    Send(sock, buf, strlen(buf));

    return 0;
}

//设置socket为非阻塞
void setnonblocking(int sockfd) {
    int opts;
    opts = fcntl(sockfd, F_GETFL);
    if (opts < 0) {
        perror("fcntl(F_GETFL)\n");
        exit(1);
    }
    opts = (opts | O_NONBLOCK);
    if (fcntl(sockfd, F_SETFL, opts) < 0) {
        perror("fcntl(F_SETFL)\n");
        exit(1);
    }
}
int main() {
    int listenfd, conn_sock, epfd;
    char buf[BUFSIZ];
    socklen_t clilen;
    struct sockaddr_in cliaddr, servaddr;
    struct epoll_event ev, events[MAX_EVENTS];
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd < 0) {
        printf("create socket error\n");
        return -1;
    }
    int on = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on));
    setnonblocking(listenfd);
    struct linger {
        int l_onoff; /* 0 = off, nozero = on */
        int l_linger; /* linger time */
    }lin;
    lin.l_onoff = 1;
    lin.l_linger = 0;
    setsockopt(listenfd, SOL_SOCKET, SO_LINGER, (char*)&lin, sizeof(lin));
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(PORT);

    if(bind(listenfd,(struct sockaddr*)&servaddr,sizeof(struct sockaddr))<0){
        printf("bind error\n");
        close(listenfd);
        return -1;
    }

    if(listen(listenfd, 5) < 0) {
        printf("listen error\n");
        close(listenfd);
        return -1; 
    }
    epfd = epoll_create(MAX_EVENTS); //生成epoll专用的文件描述符
    if (epfd == -1) {
        printf("epoll_create\n");
        return -1;
    }
    ev.events = EPOLLIN | EPOLLET; //设置处理的事件类型,设置为边沿触发
    ev.data.fd = listenfd;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, listenfd, &ev) == -1) {
        printf("epoll_ctl add listen_sock fail\n");
        close(listenfd);
        return -1;
    }
    while (1) {
        int timeout = 1000; 
        int nfds = epoll_wait(epfd, events, MAX_EVENTS, timeout);
        if (nfds == -1) {
            printf("epoll_wait\n");
            return -1;
        }
        for (int i = 0;i < nfds; ++i) {
            int fd = events[i].data.fd;
            if (fd == listenfd) { //监听事件
                while ((conn_sock = accept(listenfd, NULL, NULL)) > 0) {//循环处理accept,这样可以处理多个连接在就绪队列中的情况
                    printf("accept %d\n", conn_sock);
                    setnonblocking(conn_sock);
                    ev.events = EPOLLIN | EPOLLET; //设置为边沿触发
                    ev.data.fd = conn_sock;
                    if (epoll_ctl(epfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) {
                        printf("epoll_ctl: add fail\n");
                        close(conn_sock);
                        return -1;
                    }
                }
            } else if (events[i].events & EPOLLIN) {//读事件，说明有数据从客户端发来
                int n = 0;
                int nread = 0;
                while ((nread = read(fd, buf + n, BUFSIZ - n)) > 0) {
                    n += nread;
                }
                if (nread == -1 && errno != EAGAIN) {//读数据错误,关闭描述符
                    printf("read error\n");
                    close(fd); //关闭一个描述符，它会从epoll描述符集合中自动删除
                    continue;
                }
                if(nread == 0) { //客户端关闭连接，关闭相应的描述符
                    close(fd);
                    continue;
                }
                if( n > 0) {
                    process_command(fd, buf);
                    memset(buf, 0, sizeof(buf));
                }
            }
        }
    }
}

联系作者

欧拉工程-问题58

By robinjia

發表於 2013-09-02

原题链接http://projecteuler.net/problem=58

Spiral primes

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ~ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

螺旋素数
从1开始以如下方式逆时针螺旋，可以得到一个大小为7的螺旋方块

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

有趣的是奇数的平方都在对角线的右下角，更有趣的是，13个位于对角线的数中，有8个是素数；比率是8/13 约等于 62%。

如果像上面的螺旋那样再加一层螺旋，将得到一个大小为9的螺旋方块。如果这个步骤一直持续下去，当螺旋方块的大小为多少时，对角线上的素数比率会小于10%？

解答：
表示对角线上的数与第28题相同，最难的部分是判定一个数是否是素数，用动态生成素数表的方法不行，太大了。最后找到了米勒-拉宾素数测试法，很快。等以后有空时专门写一篇关于素数判定方法。

阿龙的学习笔记

兼济天下则达,独善其身则穷

如何判断一个数是否是素数

联系作者

欧拉工程-问题60

联系作者

欧拉工程-问题59

联系作者

crontab定时运行脚本

联系作者

在C++的sort排序中永远让比较函数对相等的值返回false

联系作者

安装Maven

联系作者

用select实现精确定时器

联系作者

用epoll提供telnet服务的代码(续)

联系作者

用epoll提供telnet服务的代码

联系作者

欧拉工程-问题58

联系作者