素数为什么是用一个数分别去除2到sqrt(这个数)

如果N不是一个质数，是合数，就必定能分解为两个数的乘积。N = X * Y

N = X * Y = sqrt(N) * sqrt(N)   ---------->    X / sqrt(N) = sqrt(N) / Y   ----------->   X >= sqrt(N) >= Y
或者 Y >= sqrt(N) >= X  

所以只需要除到sqrt(N)。

素数的定义啊！看帖子
http://bbs.itheima.com/forum.php ... d=163031&extra=

看百度百科,里面都有解答

package com.itheima; /**  * 6、 编程打印所有的3位质数，质数特点：只能被1和其本身整除  * @author Administrator  *  */ public class Test6 {          public static void main(String[] args) {                 // TODO Auto-generated method stub                 Test6 t6=new Test6();                 t6.printPrime();         }                  public void printPrime()         {                 //定义变量，k代表质数个数，j是一个变量，用于遍历质数的下标，n标示最大质数个数                 int k=0,j=0,n=200;                 //定义一个数组，用于存储求的素数                 int[] ar=new int[n];                 //初始化第一个素数                 ar[0]=2;                 for (int i=2;i<1000;i++)                 {                                                  for (j=0;j<k;j++)                         {                                         if (i%ar[j]==0)//判断该数是否整除前面的素数                                         break;                         }                         if (j==k)//存入质数                         {                                 ar[k]=i;                                 k++;                         }                 }                 for (int i=0;i<k;i++)//打印质数                 {                         if (ar[i]==0)                                 break;                         System.out.print(ar[i]+" ");                         if (i!=0 && i%20==0)//每行打印20个                                 System.out.println();                 }         }  }

kerner 发表于 2015-1-12 10:53
如果N不是一个质数，是合数，就必定能分解为两个数的乘积。N = X * Y

N = X * Y = sqrt(N) * sqrt(N)   -- ...

谢谢，有点懂了

kerner 发表于 2015-1-12 10:53
如果N不是一个质数，是合数，就必定能分解为两个数的乘积。N = X * Y

N = X * Y = sqrt(N) * sqrt(N)   -- ...

谢谢，有点懂了