算法练习：找到100以内的所有素数（质数）

  1             /*************************************
  2              *  
  3              *  20180127凌晨0:45
  4              *  
  5              *  太冷了最近 ，晚上睡不着觉，做做题目吧
  6              * 
  7              *  找到100以内的所有素数（质数）
  8              *  
  9              *  
 10              *  
 11              *  
 12              *  先来看下质数的定义：只有1和它本身两个因数的自然数
 13              *  
 14              *  如果将所有质数从小到大依次排列，那么根据定义就可以知道2是第一个质数
 15              * 
 16              *  我们将从小到大依次排列所有质数的集合记为 集合 A = {2,,......}
 17              *  
 18              *  集合 A 里面元素的个数为 N，因为有无限个质数，毫无疑问 N 的值也无穷大
 19              *  
 20              *  现在我们已经知道了1个A集合中的元素 A[0]=2 ,我们把已经找到的素数个数记为 n+1，目前 n=0
 21              *  
 22              *  
 23              *  
 24              *  无限的东西，我们的计算机无法再有限的时间里面对其进行计算
 25              *  
 26              *  因此，我们把给要解决的问题一些约束条件：找到 m 及以内的所有素数, 
 27              *  
 28              *  m为不小于2的自然数，此处暂定 m = 100。
 29              *  
 30              *  
 31              *  现在我们已经把所有信息抽象化进行定义了，我们重新来梳理一遍所有定义
 32              *  
 33              *  A :从小到大依次排列所有质数的集合
 34              *  
 35              *  A[0] : A集合中第一个元素的值，A[0]=2
 36              *  
 37              *  n+1 :已经知道了A集合中的元素的个数，n初始时值为0
 38              *  
 39              *  m :值为100
 40              *  
 41              *  i : 变量,       i 的区间为 [2,m]
 42              *  
 43              *  j : 变量， j的区间范围为 [0,n)
 44              *  
 45              *  
 46              *  所有数学问题，都是可以被抽象化定义的，其次是可被计算的
 47              *  
 48              *  接下来我们看想计算方法
 49              *  
 50              *  根据质数的性质，我们可以有以下推论：如果一个数不能被它之前的任何质数整除,那么它自己也是一个质数
 51              *  
 52              *  换句话说，一个数能被它之前的任何质数整除,那么它就不是质数，不能被它之前的任何质数整除的数是质数
 53              *  
 54              *  因此 我们只要将当前自然数 i 与小于它 的 所有已知的 n 个质数整除便可判定
 55              *  
 56              *  
 57              *  
 58              * 
 59              ************************************/
 60 
 61 
 62             int[] A = new int[100];             //质数集合
 63             A[0] = 2;
 64             int n = 0;
 65             int m = 100;
 66             int i, j;
 67 
 68             Console.WriteLine("{0}", A[n]); //输出第一个质数
 69 
 70             i = 3;
 71             while (i <= m)
 72             {
 73                 j = 0;
 74                 while (j <= n)
 75                 {
 76                     if (i % A[j] == 0)
 77                     {
 78                         //一个数能被它之前的任何质数整除,那么它就不是质数
 79                         break;
 80                     }
 81                     else
 82                     {
 83                         //与下一个素数除余
 84                         j++;
 85 
 86                         if (j > n)  
 87                         {
 88                             //不能被它之前的任何质数整除的数是质数
 89                             n++;
 90                             A[n] = i;
 91                             Console.WriteLine("{0}", A[n]);
 92                         }
 93                     }
 94                 }
 95                 i++;
 96             }
 97 
 98 
 99 
100 
101 
102             Console.ReadKey();
103 
104             /****
105              *  20180126 凌晨1:56
106              *  
107              *  写完了，睡觉
108              * 
109              * 
110              * ****/