POJ 刷题系列:2262. Goldbach's Conjecture

POJ 刷题系列:2262. Goldbach’s Conjecture

传送门:POJ 2262. Goldbach’s Conjecture

题意:

给定一个大于4的数num,求两个奇素数使得num = p1 + p2.

思路: 打一个素数表,枚举小于num的素数p1,接着二分查找num-p2是否在素数表中,有则输出答案。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Map;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201712/P2262.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static final int MAX_N = 1000000 + 16;
    boolean[] isPrime = new boolean[MAX_N];
    int[] primes = new int[MAX_N];
    int tot;

    void seive() {
        Arrays.fill(isPrime, true);
        for (int i = 2; i < MAX_N; ++i) {
            if (isPrime[i]) {
                primes[tot++] = i;
                for (int j = 2 * i; j < MAX_N; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    void solve(int num) {

        for (int i = 0; i < tot && primes[i] < num; ++i) {
            int p1 = primes[i];
            int idx = Arrays.binarySearch(primes, 0, tot, num - p1);
            if (idx >= 0) {
                out.println(num + " = " + p1 + " + " + (num - p1));
                return;
            }
        }
        out.println("Goldbach's conjecture is wrong.");
    }

    void read() {
        seive();
        while (true) {
            int num = ni();
            if (num == 0) break;
            solve(num);
        }
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\oxygen_workspace\\Algorithm");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        read();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }

    static class D{

        public static void pp(int[][] board, int row, int col) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < row; ++i) {
                for (int j = 0; j < col; ++j) {
                    sb.append(board[i][j] + (j + 1 == col ? "\n" : " "));
                }
            }
            System.out.println(sb.toString());
        }

        public static void pp(char[][] board, int row, int col) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < row; ++i) {
                for (int j = 0; j < col; ++j) {
                    sb.append(board[i][j] + (j + 1 == col ? "\n" : " "));
                }
            }
            System.out.println(sb.toString());
        }
    }

    static class ArrayUtils {

        public static void fill(int[][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                Arrays.fill(f[i], value);
            }
        }

        public static void fill(int[][][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                fill(f[i], value);
            }
        }

        public static void fill(int[][][][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                fill(f[i], value);
            }
        }
    }

    static class Num{
        public static <K> void inc(Map<K, Integer> mem, K k) {
            if (!mem.containsKey(k)) mem.put(k, 0);
            mem.put(k, mem.get(k) + 1);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hongten

Java Web ConnectionPool (连接池技术)

701
来自专栏后端之路

dubbo源码系列之filter的前生

dubbo的filter类似于spring的aop,提供了环绕增强功能。 参考dubbo缓存代码分析 缓存是filter的一个很典型的实现。 那么filter是...

3136
来自专栏码匠的流水账

聊聊rocketmq的BrokerHousekeepingService

本文主要研究一下rocketmq的BrokerHousekeepingService

631
来自专栏Netkiller

String boot with Apache kafka 完整的发布订阅例子

本文节选自电子书《Netkiller Java 手札》地址 http://www.netkiller.cn/ 5.21.7. 完整的发布订阅实例 上面的例子仅仅...

2926
来自专栏绿巨人专栏

[Java] Design Pattern:Code Shape - manage your code shape

2805
来自专栏机器学习入门

POJ 刷题系列:1573. Robot Motion

题意: 一张地图包含N,S,W,E的指令,从指定起点[1, p]出发,是否有一条路径能够走到地图边缘,有则输出路径数,无说明走入了死循环,输出走入循环前和循环...

19210
来自专栏机器学习入门

POJ 刷题系列:2586. Y2K Accounting Bug

POJ 刷题系列:2586. Y2K Accounting Bug 传送门:2586. Y2K Accounting Bug 题意: 有一个公司由于某个病毒使...

1925
来自专栏码匠的流水账

线程池工作窃取实例

ForkJoinPool主要用到的是双端队列,不过这里我们粗糙的实现的话,也可以不用到deque。

581
来自专栏Android知识点总结

TII--Handler的使用

612
来自专栏码匠的流水账

聊聊spring boot tomcat jdbc pool的属性绑定

本文主要研究一下spring boot tomcat jdbc pool的属性绑定

422

扫码关注云+社区