UC知道Java求素数的问题
来源：百度知道 编辑：UC知道 时间：2024/05/10 14:22:19
class DoPrimeNum {
public static void main(String[] args) {
int j;
for (int i = 2; i < 100; i++)
{
for (j = 2; j <= (int)i/2; j++)
{
if (i % j == 0)
{
break;
}
}
if (j > (int)i/2 )
{
System.out.print(" " + i);
}
}
}
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
在上面的程序中，为什么‘if (j > (int)i/2 )’才print出来呀？
请解释详细一点！谢谢
public static void main(String[] args) {
int j;
for (int i = 2; i < 100; i++)
{
for (j = 2; j <= (int)i/2; j++)
{
if (i % j == 0)
{
break;
}
}
if (j > (int)i/2 )
{
System.out.print(" " + i);
}
}
}
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
在上面的程序中，为什么‘if (j > (int)i/2 )’才print出来呀？
请解释详细一点！谢谢
调试一下就知道了
或者用1-10带进去推一下
分析：
如果i除以所有的j余数都不为零(i是素数)
那么最后j还要加1,此时j = (int)i/2 + 1
这时候j就不符合循环条件(j <= (int)i/2)了
当然不走循环体，而走到下面的判断
既然j = (int)i/2 + 1,当然满足if条件
而如果i不是素数，
在2至(int)i/2的范围内肯定存在可以整除i的j
遇到可以整除的数就直接跳出循环了
所以j根本就不会超过i的一半
结论：
根据上面分析
如果i是素数,j最后的值肯定是(int)i/2 + 1
而i如果不是素数，j最后的值肯定位于2和(int)i/2之间
所以根据这个条件(j > (int)i/2)就可以确定i是素数
相当于反正法.
因为素数只包涵1和它自身,而(int)i/2的效用就在于只计算i值的一半,因为另一半与前面的"一样".
if (i % j == 0) break; //很明显,如果等于0,就说明它不是素数,直接跳过(break)就行.
接下来就是j > (int)i/2 ,其实也就是使j位于剩下的部分,经过上面的比较,这是必然.但你要注意程序的作用域,所以这里最好写个if用来判定.