【九度OJ】题目1047：素数判定解题报告

标签（空格分隔）：九度OJ

原题地址：http://ac.jobdu.com/problem.php?pid=1047

题目描述：

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

输入：

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

输出：

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

样例输入：

样例输出：

yes

Ways

用C++还是不能一遍A.

这个题是在太简单，大一经常做。就是从2到sqrt(2)枚举，看能不能整除，如果能整除就不是素数。

注意在判断n<=1的时候不能写break;如果写了程序也就运行停止了！

另外有个技巧，就是循环判断，宁愿多算一个数也不能出现错误。

#include <stdio.h>

#include <math.h>

int main() {

    int n;

    while (scanf("%d", &n) != EOF) {

        if (n <= 1) {

            printf("no\n");

            //break;//不能写

        } else {

            bool isPrime = true;

            for (int i = 2; i <= (int) sqrt(n) + 1; i++) {

                if (n % i == 0) {

                    isPrime = false;//被整除不是素数

                    break;

                }

            }

            if (isPrime) {

                printf("yes\n");

            } else {

                printf("no\n");

            }

        }

    }

    return 0;

}

另外，是否想到BigInteger类！

简直是神器好么！直接可以判断一个数是否为素数。

这里要说明，这个判断对合数的判断是绝对正确的，对素数的判断不绝对正确，只是有很大可能性进行确认。

isProbablePrime(num)里面的参数代表判断素数的准确率为1/(2^num)，num越大代表判断准确度越高，可以看出当num=10时这个题已经能AC了。

可能有人问为什么会出现这种不确定性的结果，原因是当一个数非常大的时候，判断其是否为素数的老方法为O(sqrt(n))，这个复杂度很高的，当一个数极大时，这个运算可能需要一天甚至更久才能给出结果。

所以，史上最伟大的业余数学家费马给出了近似判定公式，可以极大优化计算复杂度，但是缺点是有可能出现判错的结果。

具体见文章：聊聊如何检测素数

import java.util.*;

import java.math.*;

public class Main{

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNext()){

            if (scanner.nextBigInteger().isProbablePrime(10)) {

                System.out.println("yes");

            } else {

                System.out.println("no");

            }

        }

    }

}

Date

2017 年 3 月 7 日

巴特西

【九度OJ】题目1047：素数判定解题报告

【九度OJ】题目1047：素数判定解题报告

题目描述：

输入：

输出：

样例输入：

样例输出：

Ways

Date

最新文章

热门文章

巴特西

【九度OJ】题目1047：素数判定 解题报告

【九度OJ】题目1047：素数判定 解题报告

题目描述：

输入：

输出：

样例输入：

样例输出：

Ways

Date

最新文章

热门文章

【九度OJ】题目1047：素数判定解题报告

【九度OJ】题目1047：素数判定解题报告