算法分析

暴力想法：

for(a = 3;;a ++)
    b = n - a;
    if(a 和 b都是质数)
    {
        print;
        break;
    }

此方法的时间复杂度是$O(n\sqrt n)$,会gg

优化解法

• 1、先预处理出$10^6$以内的所有质数，
• 2、如下伪代码

for(a = 所有质数)
    b = n - a
    if(!st[b])
    {
        print;
        break;
    }

由于从1到n中，约有$\frac{n}{lnn}$个质数，运行的次数是$10^6 + T * \frac{10^6}{ln10^6}$

时间复杂度 $10^6 + T * \frac{10^6}{ln10^6}$

Java代码

import java.util.Scanner;

public class Main {
    static int N = 1000010;
    static int[] primes = new int[N];
    static int cnt = 0;
    static boolean[] st = new boolean[N];
    static void init()
    {
        for(int i = 2;i <= N - 1;i ++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0;primes[j] * i <= N - 1;j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        init();

        while(true)
        {
            int n = scan.nextInt();
            if(n == 0) break;
            for(int i = 1;;i ++)
            {
                int a = primes[i];
                int b = n - a;
                if(!st[b])
                {
                    System.out.println(n +" = " + a + " + " + b);
                    break;
                }
            }
        }
    }
}