Question

判断101-200之间有多少个素数，并输出所有素数;

public static void main(String[] args) {
int count=0;
for(int x=101;x<=200;x++){
for(int y=2;y<x;y++){
if(x%y==0){
break;
}
if(y==x-1){
System.out.println(x);
count++;
}
}
}
System.out.println("一共有"+count+"个素数");
}
内循环中的第二个if判断语句，y==x-1,是什么意思？

Answer 1

大循环是要测试是不是质数的那个数字101-200， x表示
y是小于x的（可能）约数，对于每一个x, 这个y都从2开始（因为1一定是x的约数），一旦发现这个y是x的约数，就跳出了y的循环，去看下一个x了。
因为比如现在x是102， y是2，x被y整除，x肯定不是质数了，然后break;以后y也不用再加了。x加到103.
如果真是个质数，比如103，那么y从2增加到102都不是x的约数，这时y只比x小1了，如果y能增加到这里还没有break; 就已经可以确定x=103是质数了，所以一旦满足y==x-1，你就可以打印出x, 并给质数的count++

追问

可以简单地概括一下y==x-1的含义吗？

追答

y==x-1是判断y是否等于x-1
他的意义简单的说就是看y是不是已经达到了x-1这个大小，达到的话，说明比x小，比2大的数里面没有x的约数.

追问

y是不是已经达到了x-1这个大小，在内循环中 for(int y=2;y<x;y++)，不是已经判断了吗？

追答

对，但是它要确保同一个质数只会打印一次出来，比如x=103这个数，内循环y变了101次，每次都会运行一次那个条件的判断if(y==x-1)。你只要打印一次，程序决定在y==x-1的时候做打印和count++.

另外：这个程序可以达到目的，但显然不是最优化的。一般我们测是不是质数用的约数只用到x平方根就可以了。 for(int y=2;y<x;y++) 跟本不用循环到y<x, 到y<=math.sqrt(x)就够了，可以优化不少。你问的那个内循环里的判断也是很浪费资源的做法。不过这是题外话，跟你的问题关系不大。

追问

y==x-1的作用能这样理解吗？保证x的值，在满足素数的条件下，素数只输出一次。
如果可以这样理解，我还有一个疑问，保证满足素数的条件下，素数只输出一次，怎样想到判断条件是y==x-1的？

Answer 2

对于素数这个概念，我们自然会想到这样一个问题：怎样从自然数集合中找出素数？素数到底有多少个？

　　假设给定一个自然数N，要求出N以内的所有素数，可以这样进行：因为N以内的自然数只有三种，一种是1，一种是合数，一种是素数；我们可以象筛东西那样，先把1筛掉，然后再把合数筛掉，剩下的就是素数了，这种在自然数列中寻找素数的方法就叫做埃拉托色尼筛法(简称埃氏筛法)。

　　用筛法找出不超过N的全部素数，可以遵循下面的定理进行。

　　辅助定理1：“如果n是不大于x的合数，那么n必有一个不大于√x的素约数(符号“√”表示开平方)”(证从略)。根据辅助定理1，我们只要用不大于√x的素数作筛子，就可将不大于X以内的所有的合数筛除掉。

　　辅助定理2：“素数有无限多个”(证从略)。

　　虽然素数有无穷多个，但在自然数列中的一个相当长的数列中，却找不到一个素数，而有时会出现若p是素数，p+2也是素数的情况，所以素数的出现并无规则可言。

　　一个素数只有1和本身这两个约数，因此素数就不能再分解了。但是合数却有两个以上的素约数，那么合数能不能分解成约数全部是素数的乘积呢？答案是肯定的。

　　唯一分解定理：“任何大于1的自然数都可以分解成素数的乘积，如果不计较这些素因数的顺序，这种分解方法是唯一的”(证从略)。

　　根据唯一分解定理，欲求某自然数的倍数之数列，只要用该数乘以自然数列，即可得到该数的倍数之数列。由此可知，合数的出现是有规则可言的。埃氏筛法就是根据合数的出现是有规则可言的基础上，逐个地将不大于√x的素数的倍数筛掉。根据辅助定理1，可知，筛掉那些具有不大于√x素约数的合数，序列中已无合数的存在，剩下的就是大于√x至x的素数了。

　　在运用筛法时，就可发现，当筛除某数的倍数时，有时会遇到数列中的数已被前一个筛子所筛，这样就会造成计算上的误差。针对此种情况，在数论有一个逐步淘汰原则：

　　“设有N件事物，其中，N_i件有性质i，N_j件有性质j, ..., N_ij件兼有性质i及j，...，N_ijk件兼有性质i、j及k，...。则此事物中之既无性质i，又无性质j，又无性质k，...者之件数为

　　N-N_i-N_j-N_k-...+N_ij+...-N_ijk-...+...-...。”①。

　　根据埃氏筛法和逐步淘汰原则，数论创建了求不大于X以内的素数之函数π(x)。所谓的π(x)函数，是指：

　　π(x)=N-r-1-{r∑i=1}[N/pi]+{∑1≤ii*pj]-...

　　+(-1)r[N/pi*pj*...*pr]

这是数论中求自然数列中素数的个数问题之唯一的一个根据规律而创建的函数，而所谓的素数定理中的Lix(x)函数仅是由于计算出来的数值有接近于π(x)函数中的数值而被高斯先生提议替代π(x)函数之用。因为在π(x)函数中的取整之步骤，使得计算成为十分繁琐之事。但在Lix(x)函数中，并无所求素数的个数之任何规律，在Lix函数中，仅是对数函数的积分，而对数函数只是指数函数的反函数也。

追问

只想知道内循环中的第二个if判断语句，y==x-1,是什么意思？