黑马程序员技术交流社区

标题: 求101到200之间有多少素数？ [打印本页]

作者: qiaojinhui 时间: 2013-5-16 16:17
标题: 求101到200之间有多少素数？
本帖最后由 qiaojinhui 于 2013-5-16 22:46 编辑

求101到200之间有多少素数？
public class sushu(){
public static void main (String []args){
int count =0;
for(int i=101;i<200;i++){
boolean b=false;
for(int j=2;j<Math.sqrt(i);j++){
if(i%j==0){b=false;break} 这句话中怎么来的啊？求详解
}
}
}
}

作者: 曾大鹏 时间: 2013-5-16 16:43
检查一个正整数N是否为素数，只要把这个数N除以2到sqrt(n)之间的数如果能整除，那么表示这个数就不是素数
for(int j=2;j<Math.sqrt(i);j++){
if(i%j==0){b=false;break}
所以代码是这样的

作者: qiaojinhui 时间: 2013-5-16 18:12
知道啊！但是 j 代表的是什么？？？？？？？

作者: xiaohu1218 时间: 2013-5-16 18:56
上面的程序就是根据素数的定义来判断从101到200之间素数的个数的。
素数：除了1和它本身，没有其他的约数，那么这个数就是素数。
101到200之间的任意数 i 除了1和它本身外，最大的约数就是它的平方根Math.sqrt(i)；
因此就从2(j)开始判断这个数是否还有除了1和它本身外其他的约数;
判断j是i的约数的方法就是用i%j是否等于0 ，
如果等于0 说明j就是i的约数，那么i至少就有3个约数，i也就不是素数了
如果不等于0 说明j不是i的约数

作者: long 时间: 2013-5-16 19:03
楼主理解这个问题了吗？不明白的话，我就说一下我的见解。

作者: 飞鸟青崖 时间: 2013-5-16 19:13
先回答你的问题吧：
对于内层的循环来说，它是从2开始一直到这个数的平方根结束的，j就代表的是这些数。用i%j,就是判断该数能不能在2到它的平方根之间找到约数。如果能那么它就不是素数，所以就应该判断它的下一个数是不是素数了，这样就需要跳出内层循环（也可以继续循环下去，但这时候已经没有必要了），用的是break。如果不能，那么它就是素数。
另外，楼主你这个代码有些问题：
第一：class sushu(){}没有这种定义方法，类名后面不跟().
第二：在内层循环中for(int j=2;j<Math.sqrt(i);j++)，终止条件应该设置为：j<=Math.sqrt(i).因为一个数可以是某个素数的平方，比如121 = 11 *11.那么它就不是素数。如果不加等号，你就会把它判断成素数。
代码如下：

class E1
{
public static void main (String []args)
{
int count =0;
for(int i=101;i<200;i++)
{
boolean b=true;//默认时为真，如果它是素数，那么就可以执行内循环下面的if语句
for(int j=2;j<=Math.sqrt(i);j++)
{
if(i%j==0)
{
b=false;//当它不是素数的时置为假。
//那么就无法执行内循环下面的if语句了。
break;//这时要加分号。
}
}
if(b)
{
count++;
System.out.println(i);//输出每一个素数。
}
}
System.out.println("共有素数："+count);
}
}

复制代码

作者: 尖卡斌引 时间: 2013-5-16 20:10
本帖最后由尖卡斌引于 2013-5-16 20:15 编辑

//求101到200之间有多少素数？
class SuShu
{
      public static void main (String []args)
      {
            int count =0;
            for(int i=101;i<200;i++)
            {
                     boolean b=false;

                     int j=2;

                     int math = (int)Math.sqrt(i);  //定义一个中间的除数，减少运算次数。

                     for(;j<=math;j++)
                     {
                              if(i%j==0)                   //判断 i是否能被 j整除，如果整除这if条件满足执行if{}中的语句。
                                                                  // 其中% 是取模的意思。也就是除于 j 的余数。
                              {
                                    b=false;             //条件满足 i 被 j整除  i不是素数。置 b为假。
                                    break;                //跳出j 的循环。
                              }
                     }
                     if(j>math)                         //判断j是否超过了定义的中间除数。如果j>math.则可判断此i 是一个素数。
                              b=true;
                     if(b)
                     {
                              count++;
                              System.out.println(i+"是素数");//打印这个素数；
                     }
            }
            System.out.println("101---200之间的素数的个数是"+count);
      }
}

作者: 殇_心。 时间: 2013-5-16 20:30
如果问题已解决，请及时修改分类，否则继续提问，谢谢合作！

作者: HM张博文 时间: 2013-5-28 11:09

xiaohu1218 发表于 2013-5-16 18:56
上面的程序就是根据素数的定义来判断从101到200之间素数的个数的。
素数：除了1和它本身，没有其他的约数， ...

最大的约数就是它的平方根Math.sqrt(i)；
为什么一个正整数最大的约数是他的平方根，例如100，他最大的约数是10吗？50不是？

作者: 花心々小土豆 时间: 2013-5-28 13:57
本帖最后由花心々小土豆于 2013-5-28 14:19 编辑

HM张博文发表于 2013-5-28 11:09
最大的约数就是它的平方根Math.sqrt(i)；
为什么一个正整数最大的约数是他的平方根，例如100，他最大的约 ...

上面一大片哥们都说的很详细了！貌似没听谁说过一个正数最大的约数是它的平方根。我再给你举个小例子：
16的约数：1，2，4，8，16
仔细看，4是16的平方根，1和16是一对，2和8是对。即一个数在它的平方根之前的数都不是它的约数，平方根后面的数就不可能是（这个数和1除外）。
记住一个结论：约数（除了平方跟）都是成对的，再判断一个数是不是素数的时候，只需要检查2到其平方根之间的数就可以了。
为什么约数（除了平方跟）都是成对的？？你多举几个例子看看，如果你还想问为什么，找高等数学里数论部分内容看，那里应该有证明。

作者: xiaohu1218 时间: 2013-5-30 22:55

HM张博文发表于 2013-5-28 11:09
最大的约数就是它的平方根Math.sqrt(i)；
为什么一个正整数最大的约数是他的平方根，例如100，他最大的约 ...

不好意思，这个地方用词有误应该是需要判断的最大的约数是 Math.sqrt(i);
例如 N=a*b （假设 a<b），那么 a <=Math.sqrt(N);
如果判断出从 2 到 Math.sqrt(N) 都没有 N 的约数那么就不用再判断大于 Math.sqrt(N);
例如 23 吧只需要判断从 2 到5 有没有 23的约数就好因为( 23/5) <5
5之前没有 23的约数 5之后就更不会有 23的约数了

作者: HM张博文 时间: 2013-5-31 09:06

xiaohu1218 发表于 2013-5-30 22:55
不好意思，这个地方用词有误应该是需要判断的最大的约数是 Math.sqrt(i);
例如 N=a*b （假设 a ...

说的很好，感谢了

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

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