如何思索算法（二） 谈谈素数

如何思索算法(二) 谈谈素数

在我的第一篇博客中提到了一个很重要的公式：

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^45^4；

10000=100100；

10000=20050；

10000=50020；

10000=100010；

10000=20005；

……

10000=100001；

规律来了：

10000=100100

比100大的数200，那么10000=2005

5比100小，也就是说如果已经检查过5，检查200还有必要吗？

因此，假设n=sqrt(n)sqrt(n)

比sqrt（n）大的数我们设为x，再设n=xy

则y一定比sqrt（n）小

则我们是从1开始验证到sqrt（n）

这个比sqrt（n）小的y肯定被验证到了

故只需验证到sqrt（n）

所以检查的次数就会大大减少。

1 public static boolean isPrime(int n) {

2 int m = (int) Mathsqrt(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……

23=6

33=9

34=12

35=15

……

3333=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=6i+3;j<2000000;j+=4i+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,则表示2i+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之外的素数都是奇数！！

今天，有关素数的内容就到这里！

质数（素数也叫质数）。没有区别，就是一样的意思

数字1,既不是素数,也不是合数 有的地方说1既不是质数也不是合数，但是素数，这种说法当然是错误的

#include "stdioh"

main()

{

int m,k=0;

for(m=100;m<200;m++)

if(fun(m))

{

printf("%4d",m);

k++;

if(k%5==0)

printf("\n");

}

printf("k=%d\n",k);

}

int fun(int m)

{int i,k=1;<br/>if(m<=1) k=0;<br/>for(i=2;i<m;i++)<br/>if(m%i==0) k=0;<br/>return k;<br/>}

1、首先打开编辑器软件，在里面新的C语言文件里引入头文件并输入主函数，在主函数中输入代码：

2、然后写入判断素数的逻辑，这里先引入一个scanf函数，接受用户输入的数值存入变量，对接收的变量判断其是否为素数，判断的依据是如果能被2到n-1中的某个数整除就是素数，否则就不是。最后把判断的结果打印出来即可：

3、最后编译运行调试一下程序，按下crtl+F5编译，在d出的命令行中输入17这个素数，程序判断的结果是素数说明程序的逻辑是没有问题的。以上就是C语言判断素数的方法：

以下是求n（n由键盘在程序运行时输入）以内所有素数的程序：

#include <iostream>

using namespace std;

int isprime(int n)

{for(int i=2;ii<=n;i++)

 if(n%i==0)return 0;

return n>1;

}

int main()

{int n,i;

cin>>n;

for(i=2;i<=n;i++)

 if(isprime(i))

    cout<<i<<" ";

cout<<endl;

return 0;

}

以上就是关于如何思索算法（二） 谈谈素数全部的内容，包括:如何思索算法（二） 谈谈素数、编写程序中质数和素数有什么区别、编写一个C语言程序判断一个数是否是素数等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！