黑马程序员技术交流社区

标题: 这是一个求素数问题谁帮我看下感觉不对 [打印本页]

作者: ^o（孤8o|狼i¤F 时间: 2014-4-18 22:01
标题: 这是一个求素数问题谁帮我看下感觉不对
public class Sushu {

/**
   *判断 1 到200  之间的素数
   *算法：用一个数分别取除以2 到sqrt之间的数如果可以被整除则不是素数不可以被整除则是素数
   *分析：
   *双重for循环
   */
public static void main(String[] args) {
// TODO Auto-generated method stub
int count = 1;
System.out.println(2+"\t是素数");
for(int i=3; i<200; i++){

boolean flag = false;
for(int j=2; j<Math.sqrt(i); j ++){
if( i%j == 0){
      flag = false;
break;
}
else{
flag = true;

}
}
if(flag){
System.out.println(i+"\t是素数");
count ++;
}
}

System.out.println("素数个数是\t" +count);
}

}

2 是素数
5 是素数
7 是素数
9 是素数
11 是素数
13 是素数
17 是素数
19 是素数
23 是素数
25 是素数
29 是素数
31 是素数
37 是素数
41 是素数
43 是素数
47 是素数
49 是素数
53 是素数
59 是素数
61 是素数
67 是素数
71 是素数
73 是素数
79 是素数
83 是素数
89 是素数
97 是素数
101 是素数
103 是素数
107 是素数
109 是素数
113 是素数
121 是素数
127 是素数
131 是素数
137 是素数
139 是素数
149 是素数
151 是素数
157 是素数
163 是素数
167 是素数
169 是素数
173 是素数
179 是素数
181 是素数
191 是素数
193 是素数
197 是素数
199 是素数
素数个数是 50

作者: ^o（孤8o|狼i¤F 时间: 2014-4-18 22:03
主要是有25 和 49

作者: 2528870651 时间: 2014-4-18 22:21
看看这段代码吧

public class exp2{
public static void main(String args[]){
int i=0;
math mymath = new math();
for(i=2;i<=200;i++)
if(mymath.iszhishu(i)==true)
System.out.println(i);
}
}
class math
{
public boolean iszhishu(int x)
{
for(int i=2;i<=x/2;i++)
if (x % 2==0 )
return false;
return true;
}
}

复制代码

作者: 宋超2356 时间: 2014-4-18 22:26

public class Test {
/**
*判断 1 到200 之间的素数
*算法：用一个数分别取除以2 到sqrt之间的数如果可以被整除则不是素数不可以被整除则是素数
*分析：
*双重for循环
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int count = 1;
System.out.println(2+"\t是素数");
for(int i=3; i<200; i++){
boolean flag = false;
for(int j=2; j <= Math.sqrt(i); j ++){ //小小的改变，程序是对的，注意细节
if( i%j == 0){
flag = false;
break;
}
else{
flag = true;
}
}
if(flag){
System.out.println(i+"\t是素数");
count ++;
}
}
System.out.println("素数个数是\t" +count);
}
}

复制代码

作者: 2528870651 时间: 2014-4-18 22:31
判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，
则表明此数不是素数，反之是素数。
sqrt(49)是7，你没有把7算进去
sqrt(25)是5，你没有把7算进去

所以 for(int i=3; i<200; i++){ //这里i<=200

你的代码121,169，也都是错误答案。。 121=11*11 169 =13*13

作者: z1342802487 时间: 2014-4-18 22:43
检查一个正整数N是否为素数，最简单的方法就是试除法，将该数N用小于等于根号N的所有素数去试除，若均无法整除，则N为素数。你写的j<math.sqrt(i)没有等。改法有两种1加上等号2 j<math.sqrt(i)+1

public class Sushu
{
public static void main(String[] args)
{
int count = 1;
System.out.println(2 + "\t是素数");
for (int i = 3; i < 200; i++)
{
boolean flag = false;
for (int j = 2; j < (int)Math.sqrt(i)+1; j++)
{
if (i % j == 0)
{
flag = false;
break;
} else
{
flag = true;
}
}
if (flag)
{
System.out.println(i + "\t是素数");
count++;
}
}
System.out.println("素数个数是\t" + count);
}
}

复制代码

作者: peku 时间: 2014-4-18 23:01
本帖最后由 peku 于 2014-4-18 23:27 编辑

判断语句 j<Math.sqrt(i)有错，Math.sqrt(i)是开平方根，25能直接开平方根得到Math.sqrt(i)=5，所以 if( i%j == 0)只能判断到j=4，可以在改i为j<Math.sqrt(i)+1 即可，49同理。PS：其实还是算法没理解到位，这里判断的依据是如果一个数不是素数，就肯定能被至2的倍数个不是1和本身数整除，例如24能被12X2；4X6整除，而其中一个数必然<=这个数的平方根，而不是只有小于，因为有刚好能平方根得到整数的情况，比如25，49等等。另外其实还可以这样简写代码，注意红色部分与你的代码区别class Sushu {

      /**
      *判断 1 到200  之间的素数
      *算法：用一个数分别取除以2 到sqrt之间的数如果可以被整除则不是素数不可以被整除则是素数
      *分析：
      *双重for循环
      */
      public static void main(String[] args) {
            // TODO Auto-generated method stub
            int count = 1;
            System.out.println(2+"\t是素数");
            for(int i=3; i<200; i++){

                      boolean flag = true;
                     for(int j=2; j<=Math.sqrt(i); j ++)
                                                      {

                                    if( i%j == 0){
                                          flag = false;
                                             break;
                           }
                                          }
                     if(flag){
                              System.out.println(i+"\t是素数");
                              count ++;
                     }
            }

            System.out.println("素数个数是\t" +count);
      }

}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2