如何思索算法(二) 谈谈素数
发布网友
发布时间：2023-01-04 06:20
共1个回答
热心网友
时间：2023-10-12 21:28
在我的第一篇博客中提到了一个很重要的公式：
N=(2^n)*(3^n)*(5^n)*(7^n)*(11^n)*(13^n)*(17^n)*............
任何自然数都可以用素数的n次方的乘积表示。在本文中将主要围绕如何去判断素数进行全面的分析与思考。
素数，只能被1和它本身整除的数称之为素数。
如何判断一个数n是素数。
对于1<i<n/2，不停的判断n%i是否为0，如果不存在i使n%i==0，那么该数是素数，否则不是素数。
1
2
3
4
5
6
7
8
9
public static boolean isPrime(int n) {
int m = n/2;
for (int i = 2; i < m; i++) {//n=2时，循环不执行！！！！！！！
if (n % i == 0) {
return false;
}
}
return true;
}
注意，当判断2是否为素数时，方法体内的循环不会执行，所以针对该情况只需要将2单独处理即可。也可以修改代码，但是毫无意义。
貌似这种方法已经很不错了，可是该方法存在瑕疵，这个瑕疵叫做检查次数。如果判断10000是不是素数（当然这个例子有点蠢，只是为了说明问题，计算机可不知道10000是不是素数，就让它做一点蠢事吧），那么上述方法需要检查5000次，5000次对于我们的计算机来说，小case。问题在于，这5000次检查都是必要的吗？重新把我们的公式拿来进行分析：
N=(2^n)*(3^n)*(5^n)*(7^n)*(11^n)*(13^n)*(17^n)*............
10000=2^4*5^4；
10000=100*100；
10000=200*50；
10000=500*20；
10000=1000*10；
10000=2000*5；
……
10000=10000*1；
规律来了：
10000=100*100
比100大的数200，那么10000=200*5
5比100小，也就是说如果已经检查过5，检查200还有必要吗？
因此，假设n=sqrt(n)*sqrt(n)
比sqrt（n）大的数我们设为x，再设n=x*y
则y一定比sqrt（n）小
则我们是从1开始验证到sqrt（n）
这个比sqrt（n）小的y肯定被验证到了
故只需验证到sqrt（n）
所以检查的次数就会大大减少。
1 public static boolean isPrime(int n) {
2 int m = (int) Math.sqrt(n);
3 for (int i = 2; i <= m; i++) {//n=2时，循环不执行！！！！！！！
4 if (n % i == 0) {
5 return false;
6 }
7 }
8 return true;
9 }
就目前而言，该方法已经很不错了，对于判断10000是否是素数数我们只需要检查100次就够了。
可是，如果要求10000以内的所有素数呢？从2到10000一个一个进行判断吗？
算法是很神奇的，就看你敢不敢去探索了，素数是什么数？
偶数和奇数！！！！！！！！！！！除2之外都是奇数！！！！！！！！！！！！！
2、3、5、7、11、13、17、19……
根据这个方法我可以一下找出所有素数，干嘛还非要去一个个的去判断呢？反正我不满意！ 对于10000以内的素数，除了2之外，肯定都是奇数，我干嘛还要去检查哪些偶数呢？
3、5、7、11、13、17、19……
2*3=6
3*3=9
3*4=12
3*5=15
……
3*333=999
筛选出不是素数的奇数，最后只剩下素数。
这就是：筛选法。
1 public static void allPrimes(){
2 boolean[] is_primes = new boolean[1000000];
3 for(int i = 0;i<1000000;i++)
4 {
5 is_primes[i]=true;
6 }
7 is_primes[0]=false;
8 for(int i=1;i<1000000;i++)
9 {
10 if(is_primes[i])
11 {
12 for(int j=6*i+3;j<2000000;j+=4*i+2)
13 {
14 is_primes[j/2]=false;
15 }
16 }
17
18 }
19 }
注意：is_primes中存储奇数，is_primes[0]表示1，is_primes[1]表示3，如果is_primes[i]=true,则表示2*i+1为素数。
好，问题到这里也该差不多结束了，可是我还想啰嗦一点，因为我接下来的算法和上面的筛选法相比优势并不是很大，但是思想却是极好滴。
动态规划算法
依然是文章开始的公式，依然是求10000以内的所有素数问题。
判断一个数是否为素数，只需要判断是否存在一个小于该数的素数能被该数整除，如果不存在该数为素数，否则不是素数。
我就不一步步推理了，很好理解，这个例子应该在文中影射好多次了直接给出代码。
1 private int[] primes = new int[1000000];
2 private int length = 0;
3 public void primesOf2Million(){
4 primes[0]=2;
5 length = 1;
6 for(int i=3;i<2000000;i++){
7 boolean is_prime = true;
8 for(int j=0;j<length;j++){
9 if(i%primes[j]==0){
10 is_prime = false;
11 break;
12 }
13 }
14 if(is_prime){
15 primes[length++]=i;
16 }
17 }
18 }
注意:该示例代码求出了2000000以内的所有素数，为什么只开了1000000长度的数组，因为除了2之外的素数都是奇数！！
今天，有关素数的内容就到这里！
