题目描述：

给定一个数n，要求判断其是否为素数（0,1，负数都是非素数）。

输入：

测试数据有多组，每组输入一个数n。

输出：

对于每组输入,若是素数则输出yes，否则输入no。

样例输入：

样例输出：

yes

代码

#include <iostream>
using namespace std;
bool IS(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int n;
    while(cin>>n){
        int flag = 1;
        if(n<0 || n==0 ||n==1){
            cout<<"no"<<endl;
            flag = 0;
        }
        if(n==2){
            cout<<"yes"<<endl;
            flag = 0;
        }
        if(flag){
            if(IS(n)){
                cout<<"yes"<<endl;
            }
            else{
                cout<<"no"<<endl;
            }
        }
    }
    return 0;
}

一只狗的提醒

网上都说这个题目水，但是我还是多翻了几个，有个人用java做的，他有两种方法，我也给你弄过来了。

java

第一种方法

试除法，把每一个比它小的数都除一遍

代码

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner cin = new Scanner(System.in);
        int a;
        boolean isPrime;
        while(cin.hasNext()){
            a = cin.nextInt();
            isPrime = true;
            if(a < 2)//这里容易错，2是素数
                isPrime = false;
            else{
                for(int i = 2 ; i < a ; i++){
                    if((a % i) == 0){
                        isPrime = false;
                        break;
                    }                   
                }
            }
            if(isPrime == true)
                System.out.println("yes");
            else
                System.out.println("no"); 
        }
    }
}

改进：减少几个循环，只需除到√m即可
（原因：因为如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m）

for(int i = 2 ; i <= Math.sqrt(a) ; i++){

第二种方法

费马小定理+素数表
费马小定理：对于两个互质的素数N和P，必有：N^(P-1)%P=1
问题来了，当N和P很大时，乘方运算结果很大，而int最大只有32位，怎么办？
这时，可以把Y个X相乘再取模的过程分解开来，
比如：(17^25)%29则可分解为：( ( 17 * 17 ) % 29 * ( 17 * 17 ) % 29 * ……
这就是著名的“蒙格马利”快速幂模算法！
还要用到积模分解公式：
设有X、Y和Z三个正整数，则必有：(X*Y)%Z=((X%Z)*(Y%Z))%Z

对于给定的N，从素数表中取出任意的素数对其进行费马测试，如果取了很多个素数，N仍未测试失败，
那么则认为N是素数。当然，测试次数越多越准确，但一般来讲50次就足够了。

参考：http://blog.csdn.net/arvonzhang/article/details/8564836
和http://www.cnblogs.com/Knuth/archive/2009/09/04/1559949.html
题目拓展：

输入自然数n，要得到自然数n以内的全部素数

筛选法。即埃拉托斯特尼筛法：要得到自然数n以内的全部素数，
必须把不大于√n的所有素数的倍数剔除，剩下的就是素数。

算法如下：

代码

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = (int)Math.ceil(Math.sqrt(n));
        //初始化数组值为0  0表示是素数，1表示不是素数
        int[] arr = new int[n];
        for(int i= 2 ; i < m ; i++){
            if(arr[i] == 0){
                for(int j = 2*i ; j < n ; j = j+i){
                    arr[j] = 1;
                }
            }  
        }
        //输出结果
       for(int k = 2 ; k < n ; k++){
            if(arr[k] == 0){
                System.out.print(k + " ");
            }
       }
    }
}