题目描述
令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。
输入描述:
输入在一行中给出M和N，其间以空格分隔。
输出描述:
输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。
输入例子:
5 27
输出例子:
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103
思路和知识点：
- 素数：在大于1的整数中，只能被1和这个数本身整除的数，如2、3、5、7、11。也叫质数。（1不是素数）
- Math.sqrt(): JAVA中实现求一个数的平方根
- 如何判断一个数是否是素数?
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sann = new Scanner(System.in);
int left = sann.nextInt();
int right = sann.nextInt();
int times = 0;//用来计数
for(int i=1; ;i++){ //从1开始判断每个数是否是素数
if(isPrime(i)==true){
times++;//如果是素数，计数加一
if(times<right && times>=left){ //如果在要求的范围内，则要十个一行输出
if((times-left+1)%10 == 0 ){
System.out.print(i);
System.out.print("\n");//输出该数并换行
}else{
System.out.printf("%d ",i);//输出该数并空格
}
}
if(times == right){
System.out.printf("%d",i);
break; //跳出for循环
}
}//end if
}//end for;
}
// // 判断一个数是否是素数的方法
public static boolean isPrime(int num){
boolean flag = true;
if(num==1){
flag = false;
}
if((num == 2 || num ==3)&& num!=1){
flag = true;
}else{
for(int i=2;i<=Math.sqrt(num);i++ ){
if(num%i==0){
flag = false;
break;
}
}
}
return flag;
}
}
哈哈哈哈哈哈，这道题实在折磨了我太长时间，网上找不到能编译成功的算法，自己小白一个，从判断素数的方法一句一句写起来，中间各种报错，还是使用java不熟练，很多语句都不太会写，连数组的初始化都要百度ORZ··· 好在，经过艰苦卓绝的顽强挣扎，终于把这道题解决了，相信以后写算法的能力也能有所提升，毕竟这是严格意义上自己第一道独立解决的算法题。
在此感谢LeetCode平台，提供了算法在线编译调试的平台，让我能一步步的尝试运行，从而找到自己原始版本中的错误。
总结一下，这道题做不出来的主要错误在于逻辑错误，好几个地方都是我的if语句的逻辑没有弄明白，几个if语句之间相互并列反而没有了需要的效果。
再次，向挣扎在算法路上的自己致敬！要继续勇敢的不放弃的走下去！
开心.png
补充（以下仅是思路，没有成功实现，可以不看，特此提醒）：
在挣扎这道题的过程中，有看到关于素数判断的一些相关理论，包括孪生素数，还有“素数都在六的倍数两侧，但六的倍数两侧不一定都是素数。”作为一个严谨又充满好奇心的喵呜，我尝试了一下以六为倍数增加的方法，第一次写出来后在35这个数字这里卡住了，因为35的开平方是5，而我的for循环从7开始，所以35这个数字没有进入for循环进行判断，调整后将判断素数函数写作如下：
// // 判断一个数是否是素数的方法
public static boolean isPrime(int num){
boolean flag = true;
if(num==1){
flag =false;
}
if((num == 2 || num ==3)&& num!=1){
flag =true;
}else{
if(num%6 != 1 && num%6!=5){
flag = false;
} else{
if(num<49){ //小于7的平方的话，就不开平了
for(int i = 7;i<num-5;i+=6){
if(num%i == 0){
flag = false;
break;
}
}
}else{
for(int i = 7;i<=Math.sqrt(num);i+=6){
if(num%i == 0){
flag = false;
break;
}
}
}//end else
}//end else
}//end else
return flag;
}// end isPrime
在调试运行后，又发现25不是素数，但是根据我们的算法得到的是素数，跟着逻辑走一边，发现上述算法的确得到25时是true，说明上述算法有误。
想了一下，素数分布在6的倍数的两侧，不是在左侧就是在右侧，也有可能左右两侧都是素数（6的倍数的左右两侧都是素数时，我们将这两个素数称作孪生素数），在我们上述算法中，根据上述思想进行了以6为步数的跃进，但是从7开始+6的跃进只遍历了6的倍数的右侧，而忽略了6的左侧，而并不是每一个6的倍数的右侧数字是素数的时候，左侧也一定是素数（反之亦然）。所以这种算法在4*6=24的左侧23（是素数）、右侧25（不是素数）时，出现了判断错误。
如何解决上述错误？那就只能左右两侧都进行判断，可是这样一来，算法是不是更加复杂？还不如原始算法？？
走到这一步已经耗尽我的脑细胞了，所以戛然止步。如果有过路的读者有想法或者更好的意见，欢迎留言批评指正！
溜了溜了~~~
网友评论