Prime

質數：恰好有兩個因數的整數，一個是1，另一個則是它自己，比如整數3和5就是質數。質數的基本算法有素性測試、埃氏篩法和整數分解。

質數測試

如果d是n的因數，則易知 n = d \cdot \frac{n}{d}, 因此 n/d也是n的因數，且這兩個因數中的較小者 \min(d, n/d) <= \sqrt{n}. 因此我們只需要對前 \sqrt{n} 個數進行處理。

埃氏篩法 Sieve of Eratosthenes

質數測試針對的是單個整數，如果需要枚舉整數n以內的質數就需要埃氏篩法了。核心思想是枚舉從小到大的質數並將質數的整數倍依次從原整數數組中刪除，餘下的即爲全部質數。

區間篩法

求區間[a, b)內有多少質數？

埃氏篩法得到的是[1, n)內的質數，求區間質數時不太容易直接求解，我們採取以退爲進的思路先用埃氏篩法求得[1, b)內的質數，然後截取爲[a, b)即可。

Implementation

Java

  1. import java.util.*;
  3. public class Prime {
  4.     // test if n is prime
  5.     public static boolean isPrime(int n) {
  6.         for (int i = 2; i * i <= n; i++) {
  7.             if (n % i == 0) return false;
  8.         }
  9.         return n != 1; // 1 is not prime
  10.     }
  12.     // enumerate all the divisor for n
  13.     public static List<Integer> getDivisor(int n) {
  14.         List<Integer> result = new ArrayList<Integer>();
  15.         for (int i = 1; i * i <= n; i++) {
  16.             if (n % i == 0) {
  17.                 result.add(i);
  18.                 // i * i <= n ==> i <= n / i
  19.                 if (i != n / i) result.add(n / i);
  20.             }
  21.         }
  22.         Collections.sort(result);
  23.         return result;
  24.     }
  26.     // 12 = 2 * 2 * 3, the number of prime factor, small to big
  27.     public static Map<Integer, Integer> getPrimeFactor(int n) {
  28.         Map<Integer, Integer> result = new HashMap<Integer, Integer>();
  29.         for (int i = 2; i * i <= n; i++) {
  30.             // if i is a factor of n, repeatedly divide it out
  31.             while (n % i == 0) {
  32.                 if (result.containsKey(i)) {
  33.                     result.put(i, result.get(i) + 1);
  34.                 } else {
  35.                     result.put(i, 1);
  36.                 }
  37.                 n = n / i;
  38.             }
  39.         }
  40.         // if n is not 1 at last
  41.         if (n != 1) result.put(n, 1);
  42.         return result;
  43.     }
  45.     // sieve all the prime factor less equal than n
  46.     public static List<Integer> sieve(int n) {
  47.         List<Integer> prime = new ArrayList<Integer>();
  48.         // flag if i is prime
  49.         boolean[] isPrime = new boolean[n + 1];
  50.         Arrays.fill(isPrime, true);
  51.         isPrime[0] = false;
  52.         isPrime[1] = false;
  53.         for (int i = 2; i <= n; i++) {
  54.             if (isPrime[i]) {
  55.                 prime.add(i);
  56.                 for (int j = 2 * i; j <= n; j += i) {
  57.                     isPrime[j] = false;
  58.                 }
  59.             }
  60.         }
  61.         return prime;
  62.     }
  64.     // sieve between [a, b)
  65.     public static List<Integer> sieveSegment(int a, int b) {
  66.         List<Integer> prime = new ArrayList<Integer>();
  67.         boolean[] isPrime = new boolean[b];
  68.         Arrays.fill(isPrime, true);
  69.         isPrime[0] = false;
  70.         isPrime[1] = false;
  71.         for (int i = 2; i < b; i++) {
  72.             if (isPrime(i)) {
  73.                 for (int j = 2 * i; j < b; j += i) isPrime[j] = false;
  74.                 if (i >= a) prime.add(i);
  75.             }
  76.         }
  77.         return prime;
  78.     }
  80.     public static void main(String[] args) {
  81.         if (args.length == 1) {
  82.             int n = Integer.parseInt(args[0]);
  83.             if (isPrime(n)) {
  84.                 System.out.println("Integer " + n + " is prime.");
  85.             } else {
  86.                 System.out.println("Integer " + n + " is not prime.");
  87.             }
  88.             System.out.println();
  90.             List<Integer> divisor = getDivisor(n);
  91.             System.out.print("Divisor of integer " + n + ":");
  92.             for (int d : divisor) System.out.print(" " + d);
  93.             System.out.println();
  94.             System.out.println();
  96.             Map<Integer, Integer> primeFactor = getPrimeFactor(n);
  97.             System.out.println("Prime factor of integer " + n + ":");
  98.             for (Map.Entry<Integer, Integer> entry : primeFactor.entrySet()) {
  99.                 System.out.println("prime: " + entry.getKey() + ", times: " + entry.getValue());
  100.             }
  102.             System.out.print("Sieve prime of integer " + n + ":");
  103.             List<Integer> sievePrime = sieve(n);
  104.             for (int i : sievePrime) System.out.print(" " + i);
  105.             System.out.println();
  106.         } else if (args.length == 2) {
  107.             int a = Integer.parseInt(args[0]);
  108.             int b = Integer.parseInt(args[1]);
  109.             List<Integer> primeSegment = sieveSegment(a, b);
  110.             System.out.println("Prime of integer " + a + " to " + b + ":");
  111.             for (int i : primeSegment) System.out.print(" " + i);
  112.             System.out.println();
  113.         }
  114.     }
  115. }