素数小探索

• 题目：写一个程序判断一个数是否是素数。

  • 直接利用定义敲代码：

       boolean isprime(int n) {
       		for(int i=2; i<n; ++i) {
       			if(n%i==0)return false;
       		}
       		return true;
       	}
    

  • 对正整数n，如果用2到sqrt(n)之间的所有整数去除，均无法整除，则n为质数。显然for循环还可以继续优化：

       boolean isprime(int n) {
       		for(int i=2; i*i<=n; ++i) {
       			if(n%i==0)return false;
       		}
       		return true;
       	}
    

    ​

• 现在我们换个提法：求1-100内的素数。

  • 思路同样简单，只是加个for循环：

         for (int i = 2; i < 100; i++) {
         			if(isprime(i))
         				System.out.print(i+" ");
         		}
    

  • 但如果求1-10000内（甚至是更高）的素数，那么运行起来就太慢了，如何解决？我想也许我们可以多花些空间来代替时间，也就是说先将素数创造出来；我们知道2是素数，但2的倍数就不是，如4、6等，同样的道理可以推广到所有素数，那么我们就可以先将素数的倍数设为0，那么遍历完后，剩余的 !0数就是素数了。

         void creat_prime(int value,int a[]) {	//value代表当前素数，调用时初始为2
         		//排除2,3等素数的倍数，剩余的非0就是素数
         		for (int i =2; i * value < n; i++) {
         			a[i * value]=0;
         		}
         		for (int i =value+1; i < n; i++) {
         				if(a[i]!=0) {
         					value=a[i];
         					creat_prime(value, a);
         					break;
         				}
         			}
         		}     		
    

    第一个for循环先排除2的倍数，第二个for循环是寻找下一个最小的素数（在这里就是3），然后递归函数，直至将1-n内的数全部遍历。

  • 运行后会发现个问题，太多次的递归调用会导致内存溢出

  （java.lang.StackOverflowError），真是让人头疼，仔细观察，是我想复杂了，其实只需两层for循环就可以代替上面的递归调用，而且效率更高，代码也更简洁：

       //先初始化boolean []isPrime为true（此处省略），将非素数改为false
       for (int i = 2; i * i < n; i++) {
             if (!isPrime[i]) continue;		//跳过非素数
             for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
             }
          }
  

• 题目：Count Primes

  Description:
  Count the number of prime numbers less than a non-negative number, n.
  https://leetcode.com/problems/count-primes/#/description
  

  该题就是素数优化的应用了，跟上面的最优化代码完全一致。

    public int countPrimes(int n) {
    boolean []isPrime =new boolean[n];
    for (int i = 2; i < n; ++i) {
      isPrime[i]=true;
    }
  
    //排除2,3等素数的倍数，剩余的true就是素数
    for (int i = 2; i * i < n; i++) {
          if (!isPrime[i]) continue;
          for (int j = i * i; j < n; j += i) {
            isPrime[j] = false;
          }
       }
  
    int count=0;
        for(int i=2;i<n;++i){
            if(isPrime[i])
                count++;
        }
    return count;
  }
  

  #相关： 求前n个质数的乘积

    <a href="https://jackpon.github.io/site/School/%E5%88%86%E8%A7%A3%E8%B4%A8%E5%9B%A0%E6%95%B0/">分解质因数</a>