目录
1.什么是素数
2.解法
方法零:博君一笑法
方法一:常规遍历
方法二:折半遍历--改进法
方法三:根号遍历--超级改进法
1.什么是素数
素数又称质数。一个大于1的自然数,
除了1和它自身外,不能被其他自然数整除的数叫做质数
2.解法
方法零:博君一笑法
public static void main(String[] args) { int a = 0; while (a <= 100) { if (a == 3 | a == 5 | a == 7) { //疯狂的逻辑判断 暴力到自己害怕 System.out.print(a+"\t"); //完全的不动脑子 } //我就是墨菲特! 0.O if (a % 2 != 0 & a % 3 != 0 & a % 5 != 0 & a % 7 != 0) { System.out.print(a+"\t"); } //1 3 5 7 11 13 17 19 23 29 31 //37 41 43 47 53 59 61 67 71 // 73 79 83 89 97 a++; } }
方法一:常规遍历
缺点:遍历次数太多
public class PrimeNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int i = 2; //i从2开始遍历,因为素数的因数包含1和它本身
for (; i < num; i++) { //从2遍历到输入数之前
if (num % i == 0) { // 当有数字可以将num余尽时,打印输出,并结束循环
System.out.println("不是素数");
break;
}
}
if (i == num) { //当i等于输入数时,此时因数只有1和它本身,所以是素数
System.out.println("是素数");
}
sc.close();
}
}
方法二:折半遍历--改进法
当输入数越大时,它成为其他数的倍数的概率会变大
同时,如果已经确定不是素数的数,后面它的倍数就不必遍历计算了
我们判断数值的一半范围内,该数有没有被整除 (除 1 外)
会被整除就不是素数,不会整除就是素数
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int i = 2; //i从2开始遍历,因为素数的因数包含1和它本身
for (; i <= num / 2; i++) { //从2遍历到输入数的一半
if (num % i == 0) { // 当有数字可以将num余尽时,打印输出,并结束循环
System.out.println("不是素数");
break;
}
}
if (i > num / 2) { //当i大于输入数一半时,此时因数只有1和它本身,所以是素数
System.out.println("是素数");
}
sc.close();
}
方法三:根号遍历--超级改进法
原理同上,比起一半的范围,缩小至根数的范围更加高效文章来源:https://www.toymoban.com/news/detail-846231.html
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int i = 2; for (; i <= Math.sqrt(n); i++) { if (n % i == 0) { System.out.println("不是素数"); break; } } if (i > Math.sqrt(n)) { System.out.println("是素数"); } sc.close(); }
public static void main(String[] args) { Scanner scanner = new Scanner (System.in); int count = 0; int n = scanner.nextInt(); for (int i = 2; i <= n; i++) { int sign = 1; for (int j = 2; j <= Math.sqrt(i) ; j++) { if(i % j == 0) { sign = 0; break; } } if(sign == 1) { System.out.print(i+"\t"); } } scanner.close(); }
打印n以内的素数文章来源地址https://www.toymoban.com/news/detail-846231.html
到了这里,关于Java 求素数 (四种方法,依次改进)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!