UC知道一个Java程序：求100-200的素数？
来源：百度知道 编辑：UC知道 时间：2024/05/15 15:52:21
程序如下：
public class PrimeNumber{
public static void main(String args[]){
System.out.println("****prime numbers between 100 and 200 ****");
int n=0;
outer:for(int i=101;i<200;i+=2){
int k=15;
for(int j=2;j<=k;j++){
if(i%j==0)
continue outer;
}
System.out.print(" "+i);
n++;
if(n<10)
continue;
System.out.println();
n=0;
}
System.out.println();
}
}
请问：这里面为什么设k=15，难道素数只除从2到15吗？？？？
public class PrimeNumber{
public static void main(String args[]){
System.out.println("****prime numbers between 100 and 200 ****");
int n=0;
outer:for(int i=101;i<200;i+=2){
int k=15;
for(int j=2;j<=k;j++){
if(i%j==0)
continue outer;
}
System.out.print(" "+i);
n++;
if(n<10)
continue;
System.out.println();
n=0;
}
System.out.println();
}
}
请问：这里面为什么设k=15，难道素数只除从2到15吗？？？？
我写个函数给你，虽然我学的不是java但是算法是通用的你可以看看：
// 检验一个数是否为质数的函数：
bool isPrime (int number)
{
if(number < 0)
number = -number;
// 0和1都是质数
if (number == 0 || number == 1)
{
return true;
}
for (divisor = number/2; number%divisor != 0; --divisor)
{
;
}
return divisor == 1;
}
// 在你的问题中可以这样用：
for(int i = 100; i < 200; ++i)
{
if(isPrime(i))
System.out.print(" "+i);
}
14的平方是196,小于200.15的平方225,大于200.如此而已.
因为,如果100-200中的一个数z不是质数,那么z=x*y(x,y不为1),x,y中必有一个小于15.
如果不是这样,那么,x,y都大于15,z=x*y>15*15=225>200,显然与z<200矛盾,
之所以选择15,是因为x=y=14时,存在z=196=x*y.
这样写可以减少for循环的执行次数,提高效率.
用常规的方法,第二个for循环应写为
for(int j=2;j<=i/2;j++),这样会执行更多次数,效率不高.