素数的妙用---一道关于字符串的面试题

何为素数？只能被自己和1整除的数。

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

#include<stdio.h>
int main()
{
        int i,j;
        for(i = 2;i <= 1000;i++){
                int flag = 1;//init >>>yes prime
                for(j = 2;j <= i-1;j++)
                        if(i%j == 0){
                                flag = 0;//no prime
                                break;}
                if(flag)
                printf("%d ",i);
                }
        printf("\n");
}

上诉方法利用了：只要一个给定的数i 能被2到i-1之间任意一个数整除就说明这个数i不是素数 置标志flag=0 跳出循环判断下一个给定的数。

还有一种判断方法，速度能快一些 依据是：

　“根据质数的定义，在判断一个数n是否是质数时，我们只要用1至n-1去除n，看看能否整除即可。但我们有更好的办法。先找一个数m，使m的平方大于n，再用<=m的质数去除n（n即为被除数），如果都不能整除，则n必然是质数。如我们要判断1993是不是质数，50*50>1993，那么我们只要用1993除以<50的质数看是否能整除，若不能即为质数。100以内的质数有25个，还是比较好记的，我们只要记熟100以内质数，就可以快速判断10000以内的数是不是质数了。”【百度百科】

调用个库函数sqrt就可以了。。。

#################################分割线###########################

一道华丽的面试题：判断字串中的字符是否都在母串中出现过（不是KMP，比那个简单多了）

A：ABMQHPZDN

B：QHPZD

________________________TRUE

A：ABMQHPZDN

B：QHPZDC

________________________FASLE

C没出现过；

o（n*m）复杂度的很简单，有没有更加优化的算法呢?素数可以在此大展身手。

将每一个字符分配一个素数：A:2 B:3 M:5 Q:7 H:11 P:13 Z:17 D:19 N:23

并将其相乘#define MAX_LONG 2*3*5*7*11*13*17*19*23

后用（MAX_LONG % 字串中出现字母对应的素数 ） == 0 ------>在母串中出现过。else NO FOUND！

0（1）.....