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

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

---

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

题目描述：

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

输入：

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

输出：

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

样例输入：

13

样例输出：

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 日